Gorav Jindal

SODA Conference 2024 Conference Paper

On the Hardness of PosSLP

• Peter Bürgisser
• Gorav Jindal

The problem PosSLP involves determining whether an integer computed by a given straight-line program is positive. This problem has attracted considerable attention within the field of computational complexity as it provides a complete characterization of the complexity associated with numerical computation. However, non-trivial lower bounds for PosSLP remain unknown. In this paper, we demonstrate that PosSLP ∈ BPP would imply that NP ⊆ BPP, under the assumption of a conjecture concerning the complexity of the radical of a polynomial proposed by Dutta, Saxena, and Sinhababu (STOC’2018). Our proof builds upon the established NP -hardness of determining if a univariate polynomial computed by an SLP has a real root, as demonstrated by Perrucci and Sabia (JDA’2005).

SODA Conference 2019 Conference Paper

A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials

• Vishwas Bhargava
• Markus Bläser
• Gorav Jindal
• Anurag Pandey 0001

STOC Conference 2018 Conference Paper

Generalized matrix completion and algebraic natural proofs

• Markus Bläser
• Christian Ikenmeyer
• Gorav Jindal
• Vladimir Lysikov

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 653–664, 2017) and independently by Grochow, Kumar, Saks and Saraf (CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich’s famous barrier result (J. Comput. Syst. Sci., 55(1): 24–35, 1997) for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich’s barrier result relies on a widely believed assumption, namely, the existence of pseudo-random generators. Unfortunately, there is no known analogous theory of pseudo-randomness in the algebraic setting. Therefore, Forbes et al. use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al. are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.