2 citations · 4 across the 11 of their papers we have counts for
10 papers · 1 filter
Deterministic NC Quadratic Root Counting in Characteristic Two
Sanyam Agarwal, Gorav Jindal
Counting satisfying assignments of Boolean formulas is a basic problem in theoretical computer science, with $\#3\text{-}\SAT$ as the standard $\SharpP$-complete problem. More gene…
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…
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…
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…
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…
Homogeneous Algebraic Complexity Theory and Algebraic Formulas
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were origi…
On the Hardness of PosSLP
Peter Bürgisser, Gorav Jindal
The problem involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention withi…
On the Order of Power Series and the Sum of Square Roots Problem
Louis Gaillard, Gorav Jindal
This paper focuses on the study of the order of power series that are linear combinations of a given finite set of power series. The order of a formal power series, known as $\text…
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…
Subtraction makes computing integers faster
Thatchaphol Saranurak, Gorav Jindal
We show some facts regarding the question whether, for any number , the length of the shortest Addition Multiplications Chain (AMC) computing is polynomial in the length of…