Open Seminar of Pranjal Dutta Time: May 12, 2022 11:00 AM India A Tale of Hardness, Derandomization & Debordering in Complexity Theory Pranjal Dutta Chennai Mathematical Institute. 120522 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 polynomialtime 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 nontrivial lower bounds for representing a univariate polynomial as a sumofsquares (SOS), (ii) bounding the number of real roots of explicit univariate polynomials, and (iii) the bigticket 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 depth4. Depth4 circuits are known to be surprisingly powerful [AV08; Koi12]. In this work, we quasiderandomize 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 topfan in2 depth3 circuits (\Sigma^{[2]}\Pi\Sigmabar) circuits. In a joint work with Prateek Dwivedi and Nitin Saxena, that appeared in FOCS’21, we show that the border of bounded topfanin depth3 circuits (\Sigma^{[k]}\Pi\Sigma, for constant k) is ‘relatively easy’ – it can be computed by a polynomialsize algebraic branching program (ABP). Moreover, we give the first quasipolynomialtime blackbox identity test for the same. Before our work, there were hardly strong debordering and derandomization results known for interesting, restricted models.
