PUBLIC VIVA-VOCE NOTIFICATION
Tuesday, 27 July 2021, 2.45 pm
Algebraic Circuit Complexity: New Lower Bounds, Algorithms, and Applications
Rajit Datta
Chennai Mathematical Institute.
27-07-21

---

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 (non-monotone) depth-3 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 non-monotone 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 multi-tape weighted automata [Freidman & Greibach 82]. We give the first deterministic quasi-polynomial 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 non-commutative and non-associative model. [Hrubes, Wigderson, and Yehudayoff 10] have studied the commutative non-associative model and proved completeness and lower bound results. Over non-commutative and non-associative 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.