PUBLIC VIVAVOCE NOTIFICATION Tuesday, 27 July 2021, 2.45 pm Algebraic Circuit Complexity: New Lower Bounds, Algorithms, and Applications Rajit Datta Chennai Mathematical Institute. 270721 Abstract Algebraic Circuit Complexity is a subfield of complexity theory which studies the efficiency of computing polynomials. This thesis provides contributions on both the lower bound aspect as well as the algorithmic aspects of Algebraic Circuit Complexity. On the lower bound side, we study monotone algebraic circuits and prove new lower bound results. Most notably, using techniques from communication complexity, we exhibit a polynomial family computable by (nonmonotone) depth3 circuit which requires monotone algebraic circuits of exponential size. This improves the results of [Valiant 78] and [Jerrum & Snir 82] and provides a qualitatively optimal separation between monotone and nonmonotone computation. The contribution on the algorithmic side is three fold. Our first algorithmic result makes progress in an important problem of algebraic automata theory which asks to design efficient deterministic algorithm for testing equivalence of multitape weighted automata [Freidman & Greibach 82]. We give the first deterministic quasipolynomial time algorithm for the equivalence testing of $k$tape weighted automata for constant $k$. Our algorithm is obtained by designing a $\PIT$ algorithm for algebraic branching programs over certain partially commutative domains. The next chapter of the thesis deals with $\PIT$ and irreducibility testing over the noncommutative and nonassociative model. [Hrubes, Wigderson, and Yehudayoff 10] have studied the commutative nonassociative model and proved completeness and lower bound results. Over noncommutative and nonassociative domain, we complement their result by designing efficient deterministic identity testing and irreducibility testing algorithms. In the final chapter of the thesis, we study the ideal membership problem from the perspective of parameterized complexity and design new algorithms for various special cases. Two of the main applications are a new algorithm for computing the permanent of low rank matrices and an algorithm for detecting vertex covers in graphs whose adjacency matrices have low rank.
