2 citations · 4 across the 11 of their papers we have counts for
Showing 2024Show all
3 papers · 1 filter
cs.CC2024
On the Counting Complexity of the Skolem Problem
Gorav Jindal, Joël Ouaknine
The Skolem Problem asks, given an integer linear recurrence sequence (LRS), to determine whether the sequence contains a zero term or not. Its decidability is a longstanding open p…
cs.CC2024
PosSLP and Sum of Squares
Markus Bläser, Julian Dörfler, Gorav Jindal
The problem PosSLP is the problem of determining whether a given straight-line program (SLP) computes a positive integer. PosSLP was introduced by Allender et al. to study the comp…
cs.CC2024
Fixed-parameter debordering of Waring rank
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has…