Publications

2024

1. arXiv

   PosSLP and Sum of Squares

   Markus Bläser, Julian Dörfler, and Gorav Jindal

   2024

   arxiv
2. STACS

   Fixed-Parameter Debordering of Waring Rank

   Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

   In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), 2024

   Abtract

   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 low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering is at the heart of understanding the difference between Valiant’s determinant vs permanent conjecture, and Mulmuley and Sohoni’s variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known. In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5.

3. ITCS

   Homogeneous Algebraic Complexity Theory and Algebraic Formulas

   Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

   In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), 2024

   Abtract

   We study algebraic complexity classes and their complete polynomials under homogeneous linear projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the first complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM ’18). This requires a careful study of circuits with arity-3 product gates.

4. SODA

   On the Hardness of PosSLP

   Peter Bürgisser, and Gorav Jindal

   In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024

   Abtract

   Abstract 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).

2023

1. ISSAC

   On the Order of Power Series and the Sum of Square Roots Problem

   Louis Gaillard, and Gorav Jindal

   In Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, 2023

   Abtract

   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 , is defined as the minimum exponent of x that has a non-zero coefficient in f(x). Our first result is that the order of the Wronskian of these power series is equivalent up to a polynomial factor, to the maximum order which occurs in the linear combination of these power series. This implies that the Wronskian approach used in (Kayal and Saha, TOCT’2012) to upper bound the order of sum of square roots is optimal up to a polynomial blowup. We also demonstrate similar upper bounds, similar to those of (Kayal and Saha, TOCT’2012), for the order of power series in a variety of other scenarios. We also solve a special case of the inequality testing problem outlined in (Etessami et al., TOCT’2014). In the second part of the paper, we study the equality variant of the sum of square roots problem, which is decidable in polynomial time due to (Blömer, FOCS’1991). We investigate a natural generalization of this problem when the input integers are given as straight line programs. Under the assumption of the Generalized Riemann Hypothesis (GRH), we show that this problem can be reduced to the so-called “one dimensional” variant. We identify the key mathematical challenges for solving this “one dimensional” variant.

2022

1. arXiv

   De-bordering and Geometric Complexity Theory for Waring rank and related models

   Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

   2022

   Abtract arxiv

   De-bordering is the task of proving that a border complexity measure is bounded from below, by a non-border complexity measure. This task is at the heart of understanding the difference between Valiant’s determinant vs permanent conjecture, and Mulmuley and Sohoni’s Geometric Complexity Theory (GCT) approach to settle the P 6= NP conjecture. Currently, very few de-bordering results are known. In this work, we study the question of de-bordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures, in the context of invariant theory, algebraic geometry and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous results were known to be exponential in the degree. 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 linear polynomials. We prove the converse of Kumar’s result, and in this way we de-border Kumar’s complexity, and obtain a new formulation of border Waring rank, up to a factor of the degree. We phrase this new formulation as the orbit closure problem of the product-plus-power polynomial, and we successfully de-border this orbit closure. We fully implement the GCT approach against the power sum, and we generalize the ideas of Ikenmeyer-Kandasamy (STOC’20) to this new orbit closure. In this way, we obtain new multiplicity obstructions that are constructed from just the symmetries of the points and representation theoretic branching rules, rather than explicit multilinear computations. Furthermore, we realize that the generalization of our converse of Kumar’s theorem to square matrices gives a homogeneous formulation of Ben-Or and Cleve (SICOMP’92). This results for the first time in a VF-complete family under homogeneous projections. We study this approach further and obtain that a homogeneous variant of the continuant polynomial, which was studied by Bringmann, Ikenmeyer, Zuiddam (JACM’18), is VQP-complete under homogeneous border qp-projections. Such results are required to set up the GCT approach in a way that avoids the no-go theorems of Bürgisser, Ikenmeyer, Panova (JAMS’19)

2021

1. CCC

   Arithmetic Circuit Complexity of Division and Truncation

   Pranjal Dutta, Gorav Jindal, Anurag Pandey, and Amit Sinhababu

   In 36th Computational Complexity Conference (CCC 2021), 2021

   Abtract

   Given polynomials \(f,g,h ∈𝔽[x_1,\ldots,x_n]\)such that \(f = g/h\), where both \(g\)and \(h \)are computable by arithmetic circuits of size \(s\), we show that \(f \)can be computed by a circuit of size \(poly(s,\deg(h))\). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). The result is an exponential improvement over Strassen’s classic result (Strassen’73) when \(\deg(h)\)is \(poly(s)\)and \(\deg(f)\)is \(\exp(s)\), since the latter gives an upper bound of \(poly(s, \deg(f))\). Further, we show that any univariate polynomial family \((f_d)_d\), defined by the initial segment of the power series expansion of rational function \(g_d(x)/h_d(x)\)up to degree \(d\) (i.e. \(f_d = g_d/h_d \bmod (x^d+1)\)), where circuit size of \(g\)is \(s_d\)and degree of \(g_d\)is at most \(d\), can be computed by a circuit of size \(poly(s_d,\deg(h_d),\log(d))\). We also show a hardness result when the degrees of the rational functions are high (i.e. \(Ω(d)\)), assuming hardness of the integer factorization problem. Finally, we extend this conditional hardness to simple algebraic functions as well, and show that for every prime \(p\), there is an integral algebraic power series with its minimal polynomial satisfying a degree p polynomial equation, such that its initial segment is hard to compute unless integer factoring is easy, or a multiple of \(n!\)is easy to compute. Both, integer factoring and computation of multiple of \(n!\), are believed to be notoriously hard. In contrast, we show examples of transcendental power series whose initial segments are easy to compute.

2020

1. ISSAC

   How Many Zeros of a Random Sparse Polynomial Are Real?

   Gorav Jindal, Anurag Pandey, Himanshu Shukla, and Charilaos Zisopoulos

   2020

   Abtract

   We investigate the number of real zeros of a univariate k-sparse polynomial f over the reals, when the coefficients of f come from independent standard normal distributions. Recently Bürgisser, Ergür and Tonelli-Cueto showed that the expected number of real zeros of f in such cases is bounded by [EQUATION]. In this work, we improve the bound to [EQUATION] and also show that this bound is tight by constructing a family of sparse support whose expected number of real zeros is lower bounded by [EQUATION]. Our main technique is an alternative formulation of the Kac integral by Edelman-Kostlan which allows us to bound the expected number of zeros of f in terms of the expected number of zeros of polynomials of lower sparsity. Using our technique, we also recover the O (log n) bound on the expected number of real zeros of a dense polynomial of degree n with coefficients coming from independent standard normal distributions.

2019

1. SODA

   A Deterministic PTAS for the Algebraic Rank of Bounded Degree Polynomials

   Vishwas Bhargava, Markus Bläser, Gorav Jindal, and Anurag Pandey

   In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

   Abtract

   We present a deterministic polynomial time approximation scheme (PTAS) for computing the algebraic rank of a set of bounded degree polynomials. The notion of algebraic rank naturally generalizes the notion of rank in linear algebra, i.e., instead of considering only the linear dependencies, we also consider higher degree algebraic dependencies among the input polynomials. More specifically, we give an algorithm that takes as input a set of polynomials with degrees bounded by d, and a rational number ∊ > 0 and runs in time , where M(n) is the time required to compute the rank of an n × n matrix (with field entries), and finally outputs a number r, such that r is at least (1 – ∊) times the algebraic rank of f. Our key contribution is a new technique which allows us to achieve the higher degree generalization of the results by Bläser, Jindal, Pandey (CCC’17) who gave a deterministic PTAS for computing the rank of a matrix with homogeneous linear entries. It is known that a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets, Impagliazzo, STOC’03). Such a higher degree generalization is already known to a much stronger extent in the non-commutative world, where the more general case in which the entries of the matrix are given by polysized formulas reduces to the case where the entries are given by linear polynomials using Higman’s trick, and in the latter case, one can also compute the exact rank in polynomial time (Garg, Gurvits, Oliviera, Wigderson, FOCS’16, Ivanyos, Qiao, Subrahmanyam, ITCS’17). Higman’s trick only preserves the co-rank, hence it cannot be used to reduce the problem of rank approximation to the case when the matrix entries are linear polynomials. Thus our work can also be seen as a step towards bridging the knowledge gap between the non-commutative world and the commutative world.

2. ITCS

   On the Complexity of Symmetric Polynomials

   Markus Bläser, and Gorav Jindal

   In 10th Innovations in Theoretical Computer Science Conference (ITCS), 2019

   Abtract

   The fundamental theorem of symmetric polynomials states that for a symmetric polynomial f_Sym in C[x_1,x_2,...,x_n], there exists a unique "witness" f in C[y_1,y_2,...,y_n] such that f_Sym=f(e_1,e_2,...,e_n), where the e_i’s are the elementary symmetric polynomials. In this paper, we study the arithmetic complexity L(f) of the witness f as a function of the arithmetic complexity L(f_Sym) of f_Sym. We show that the arithmetic complexity L(f) of f is bounded by poly(L(f_Sym),deg(f),n). To the best of our knowledge, prior to this work only exponential upper bounds were known for L(f). The main ingredient in our result is an algebraic analogue of Newton’s iteration on power series. As a corollary of this result, we show that if VP != VNP then there exist symmetric polynomial families which have super-polynomial arithmetic complexity. Furthermore, we study the complexity of testing whether a function is symmetric. For polynomials, this question is equivalent to arithmetic circuit identity testing. In contrast to this, we show that it is hard for Boolean functions.

3. PhDThesis

   On Approximate Polynomial Identity Testing and Real Root Finding

   Gorav Jindal

   Saarland University, 2019

   Abtract

   In this thesis we study the following three topics, which share a connection through the (arithmetic) circuit complexity of polynomials. 1. Rank of symbolic matrices. 2. Computation of real roots of real sparse polynomials. 3. Complexity of symmetric polynomials. We start with studying the commutative and non-commutative rank of symbolic matrices with linear forms as their entries. Here we show a deterministic polynomial time approximation scheme (PTAS) for computing the commutative rank. Prior to this work, deterministic polynomial time algorithms were known only for computing a 1/2-approximation of the commutative rank. We give two distinct proofs that our algorithm is a PTAS. We also give a min-max characterization of commutative and non-commutative ranks. Thereafter we direct our attention to computation of roots of uni-variate polynomial equations. It is known that solving a system of polynomial equations reduces to solving a uni-variate polynomial equation. We describe a polynomial time algorithm for (n,k,τ)-nomials which computes approximations of all the real roots (even though it may also compute approximations of some complex roots). Moreover, we also show that the roots of integer trinomials are well-separated. Finally, we study the complexity of symmetric polynomials. It is known that symmetric Boolean functions are easy to compute. In contrast, we show that the assumption \VP≠\VNP implies that there exist hard symmetric polynomials. To prove this result, we use an algebraic analogue of the classical Newton iteration.

2018

1. TOC

   A Deterministic PTAS for the Commutative Rank of Matrix Spaces

   Markus Bläser, Gorav Jindal, and Anurag Pandey

   In Theory of Computing, 2018

   Abtract

   We consider the problem of computing the commutative rank of a given matrix space B⊆Fn×n, that is, given a basis of B, find a matrix of maximum rank in B. This problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. Finding an efficient deterministic algorithm for the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2 -approximation algorithm for the commutative rank. It is a natural question whether this approximation ratio can be improved. In this paper, we answer this question affirmatively. We present a deterministic polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space. More specifically, given a matrix space B⊆Fn×n and a rational number ϵ>0, we give an algorithm that runs in time O(n4+3/ϵ) and computes a matrix A∈B such that the rank of A is at least (1−ϵ) times the commutative rank of B. The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size k of the set depends on ϵ.

2. STOC

   Generalized Matrix Completion and Algebraic Natural Proofs

   Markus Bläser, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

   In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

   Abtract

   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. Generalized matrix completion is the following problem: Given a matrix with affine linear forms as entries, find an assignment to the variables in the linear forms such that the rank of the resulting matrix is minimal. We call this rank the completion rank. Computing the completion rank is an NP-hard problem. As our first main result, we prove that it is also NP-hard to determine whether a given matrix can be approximated by matrices of completion rank ≤ b. The minimum quantity b for which this is possible is called border completion rank (similar to the border rank of tensors). Naturally, algebraic natural proofs can only prove lower bounds for such border complexity measures. Furthermore, these border complexity measures play an important role in the geometric complexity program. Using our hardness result above, we can prove the following barrier: We construct a small family of matrices with affine linear forms as entries and a bound b, such that at least one of these matrices does not have an algebraic natural proof of polynomial size against all matrices of border completion rank b, unless coNP ⊆ ∃ BPP. This is an algebraic barrier result that is based on a well-established and widely believed conjecture. The complexity class ∃ BPP is known to be a subset of the more well known complexity class in the literature. Thus ∃ BPP can be replaced by MA in the statements of all our results. With similar techniques, we can also prove that tensor rank is hard to approximate. Furthermore, we prove a similar result for the variety of matrices with permanent zero. There are no algebraic polynomial size natural proofs for the variety of matrices with permanent zero, unless P#P ⊆ ∃ BPP. On the other hand, we are able to prove that the geometric complexity theory approach initiated by Mulmuley and Sohoni (SIAM J. Comput. 31(2): 496–526, 2001) yields proofs of polynomial size for this variety, therefore overcoming the natural proofs barrier in this case.

2017

1. CCC

   Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces

   Markus Bläser, Gorav Jindal, and Anurag Pandey

   In 32nd Computational Complexity Conference (CCC 2017), 2017

   Abtract

   We consider the problem of commutative rank computation of a given matrix space. A matrix space is a (linear) subspace of the (linear) space of n x n matrices over a given field. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively. We present a deterministic Polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space B. More specifically, given a matrix space and a rational number e > 0, we give an algorithm, that runs in time O(n^(4 + 3/e)) and computes a matrix A in the given matrix space B such that the rank of A is at least (1-e) times the commutative rank of B. The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set k depends on e.

2. APPROX/RANDOM

   Density Independent Algorithms for Sparsifying k-Step Random Walks

   Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani

   In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017), 2017

   Abtract

   We give faster algorithms for producing sparse approximations of the transition matrices of k-step random walks on undirected and weighted graphs. These transition matrices also form graphs, and arise as intermediate objects in a variety of graph algorithms. Our improvements are based on a better understanding of processes that sample such walks, as well as tighter bounds on key weights underlying these sampling processes. On a graph with n vertices and m edges, our algorithm produces a graph with about nlog(n) edges that approximates the k-step random walk graph in about m + k^2 nlog^4(n) time. In order to obtain this runtime bound, we also revisit "density independent" algorithms for sparsifying graphs whose runtime overhead is expressed only in terms of the number of vertices.

3. ISSAC

   Efficiently Computing Real Roots of Sparse Polynomials

   Gorav Jindal, and Michael Sagraloff

   In Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017

   Abtract

   We propose an efficient algorithm to compute the real roots of a sparse polynomial f∈R[x] having k non-zero real-valued coefficients. It is assumed that arbitrarily good approximations of the non-zero coefficients are given by means of a coefficient oracle. For a given positive integer L, our algorithm returns disjoint disks Δ1,...,Δs⊂C, with s<2k, centered at the real axis and of radius less than 2-L together with positive integers μ1,...,μs such that each disk Δi contains exactly μi roots of f counted with multiplicity. In addition, it is ensured that each real root of f is contained in one of the disks. If f has only simple real roots, our algorithm can also be used to isolate all real roots. The bit complexity of our algorithm is polynomial in k and log n, and near-linear in L and τ, where 2-τ and 2τ constitute lower and upper bounds on the absolute values of the non-zero coefficients of f, and n is the degree of f. For root isolation, the bit complexity is polynomial in k and log n, and near-linear in τ and logσ-1, where σ denotes the separation of the real roots.

2014

1. ISSAC

   A New Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation

   Markus Bläser, and Gorav Jindal

   In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 2014

   Abtract

   We present a deterministic algorithm to interpolate an m-sparse n-variate polynomial which uses poly(n, m, log(H), log(d)) bit operations. Our algorithm works over the integers. Here H is a bound on the magnitude of the coefficient values of the given polynomial. The degree of given polynomial is bounded by d and m is upper bound on number of monomials. This running time is polynomial in the output size. Our algorithm only requires modular black box access to the given polynomial, as introduced in [12]. As an easy consequence, we obtain an algorithm to interpolate polynomials represented by arithmetic circuits.

2013

1. MasterThesis

   Randomness Efficient Testing of Sparse Black Box Polynomials and Related Tests

   Gorav Jindal

   Saarland University, 2013

2012

1. arXiv

   Subtraction makes computing integers faster

   Gorav Jindal, and Thatchaphol Saranurak

   2012

   Abtract arxiv

   We show some facts regarding the question whether, for any number n, the length of the shortest Addition Multiplications Chain (AMC) computing n is polynomial in the length of the shortest division-free Straight Line Program (SLP) that computes n. If the answer to this question is "yes", then we can show a stronger upper bound for PosSLP, the important problem which essentially captures the notion of efficient computation over the reals. If the answer is "no", then this would demonstrate how subtraction helps generating integers super-polynomially faster, given that addition and multiplication can be done in unit time. In this paper, we show that, for almost all numbers, AMCs and SLPs need same asymptotic length for computation. However, for one specific form of numbers, SLPs are strictly more powerful than AMCs by at least one step of computation.

2008

1. BachelorThesis

   Managing Secured Documents Over Long Periods

   Gorav Jindal

   Department of Computer Science and Engineering, IIT Delhi, 2008

   Abtract

   Certificates and other legal documents play a very important role in our lives. However, currently there exists no such framework within which we can construct systems that can handle digitally secured documents over a period of say a couple of decades.This project is an attempt at analyzing the situation and then providing a suitable solution to the aforementioned problem.In this paper, we present the high level initial design with significant details of implementation of the system which can be used to address the problem. Our design and implementation is focused around creating an online degree certificate maintenance system for IIT Delhi. We will more specifically focus on on-fly generation of degree document and its verification on client side.