3 papers
cs.CC2025
Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
Markus Bläser, Sagnik Dutta, Gorav Jindal
Efficient algorithms for many problems in optimization and computational algebra often arise from casting them as systems of polynomial equations. Blum, Shub, and Smale formalized…
cs.CC2025
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.CC2025
Geometric complexity theory for product-plus-power
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of li…