|
Open Seminar of Pranjal Dutta Time: May 12, 2022 11:00 AM India A Tale of Hardness, De-randomization & De-bordering in Complexity Theory Pranjal Dutta Chennai Mathematical Institute. 12-05-22 Abstract Everyone is cordially invited to attend the Open Seminar of Pranjal Dutta. Pranjal will submit his thesis soon. His advisor is Prof Nitin Saxena in IIT Kanpur. Two of the most important problems in algebraic complexity are – (1) VP vs. VNP problem [Valiant’79]: to separate the complexity of the determinant 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 can be arbitrary constants. Next, 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, that 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.
|
