Chennai Mathematical Institute


Subject : Computer Science
Date and Time. : Tuesday, 23 August 2022, 10.30 am
Venue : Seminar Hall (Hybrid mode)
A Tale of Hardness, De-randomization & De-bordering in Complexity Theory

Pranjal Dutta
Chennai Mathematical Institute, Google PhD Fellow.


Two of the most important problems in algebraic complexity are – (1) VP vs. VNP [Valiant’79]: to separate the complexity of the symbolic determinant polynomial from that of its illustrious sibling -- the permanent, (2) Polynomial Identity Testing (PIT): to efficiently check whether the polynomial computed by a given circuit is identically zero or not. Though a very straightforward randomized algorithm exists for PIT, a deterministic polynomial-time solution has long been desired, but not yet achieved.

In two related works – (1) joint work with Nitin Saxena, and Thomas Thierauf, which appeared in ITCS’21, and (2) a single author paper that appeared in CSR’21, we study three seemingly unrelated questions and show intimate connections between them. The three questions are -- (i) showing non-trivial lower bounds for representing a univariate polynomial as a sum-of-squares (SOS), (ii) bounding the number of real roots of explicit univariate polynomials, and (iii) the big-ticket consequences in algebraic complexity (separating VP from VNP, finding an efficient algorithm for PIT, etc.).

Next, we move on to PIT results. In a joint work with Prateek Dwivedi and Nitin Saxena, which appeared in CCC’21, we study PIT for polynomials computed by some 'structured' algebraic circuits of depth-4. Depth-4 circuits are known to be surprisingly powerful [AV08; Koi12]. In this work, we quasi-derandomize two circuit classes -- (i)\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}, and, (ii)\Sigma^{[k]}\Pi\Sigma\wedge, where k and \delta are arbitrary constants. \Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]} computes polynomials of the form \sum_{i=1}^k \prod_{j} f_{ij}, where deg(f_{ij}) <= \delta, while \Sigma^{[k]}\Pi\Sigma\wedge computes polynomials of the form \sum_{i=1}^k \prod_{j} (f_{ij1}(x_1) + ....+ f_{ijn}(x_n)).

Finally, we move on to the GCT results. GGT is a novel approach toward proving strong lower bounds in complexity theory (both algebraic & Boolean), via methods from algebraic geometry and representation theory. It tries to formalize the notion of `approximating a polynomial' via limits (B\"urgisser FOCS'01). Recently (Kumar ToCT'20) proved the universal power of the border of top-fan in-2 depth-3 circuits (\Sigma^{[2]}\Pi\Sigma-bar) circuits. In a joint work with Prateek Dwivedi and Nitin Saxena, which appeared in FOCS’21, we show that the border of bounded top-fan-in depth-3 circuits (\Sigma^{[k]}\Pi\Sigma, for constant k) is 'relatively easy' -- it can be computed by a polynomial-size algebraic branching program (ABP). Moreover, we give the first quasi-polynomial-time blackbox identity test for the same. Before our work, there were hardly strong de-bordering and derandomization results known for interesting, restricted models.