Hierarchies, Circuit Lower Bounds and Pseudorandomness

The main goal of this project was to make progress on important open questions in computational complexity theory regarding complexity lower bounds for computational problems, as well as to explore new techniques to attack these questions. Together with Maurice Jansen, who was the main researcher on the project, I pursued these objectives in the context of arithmetic complexity, which studies the minimum number of arithmetic operations required to compute specified polynomials. In a series of papers published in top conferences in the area (ICALP 2011. ITCS 2012, STACS 2012), we generalized known lower bounds for computing the Permanent polynomial, and strengthened the connections between arithmetic complexity lower bounds and efficient solvability of the arithmetic circuit identity testing (ACIT) problem, which asks whether a given arithmetic circuit computes the zero polynomial.



Our results assume added significance in light of recent developments such as the Boolean circuit lower bound of Williams (CCC 2011), which take advantage of connections between lower bounds and solvability of the satisfiability problem, which is the Boolean analogue of the ACIT problem. By extending such connections to the arithmetic complexity setting, one might hope to solve long-standing open problems such as showing a super-polynomial arithmetic circuit lower bound for the Permanent. In a joint paper with Lance Fortnow (ICALP 2011), I introduced a new notion of lower bound for computational problems, and showed that Williams' lower bound could be strengthened to a lower bound under the new notion. More recently, in joint work with Williams (ECCC 2012), I showed new lower bounds for uniform circuits improving a 30-year old result of Kannan, and extended Williams' connection between the satisfiability problem and lower bounds to the validity problem for quantified Boolean formulas.