PUBLIC VIVAVOCE NOTIFICATION Subject : Computer Science Date and Time. : Tuesday, 23 August 2022, 10.30 am Venue : Seminar Hall (Hybrid mode) A Tale of Hardness, Derandomization & Debordering in Complexity Theory Pranjal Dutta Chennai Mathematical Institute, Google PhD Fellow. 230822 Abstract 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 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 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 topfan in2 depth3 circuits (\Sigma^{[2]}\Pi\Sigmabar) circuits. In a joint work with Prateek Dwivedi and Nitin Saxena, which 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.
