Hierarchies, Circuit Lower Bounds and Pseudorandomness

  • Santhanam, Rahul (Principal Investigator)

Project Details

Key findings

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.
StatusFinished
Effective start/end date1/10/1031/12/12

Funding

  • EPSRC: £125,330.00
  • On Medium-Uniformity and Circuit Lower Bounds

    Santhanam, R. & Williams, R., 2013, Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013. p. 15-23 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    File
  • Marginal hitting sets imply super-polynomial lower bounds for permanent

    Jansen, M. J. & Santhanam, R., 2012, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012. ACM, p. 496-506 11 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes

    Jansen, M. J. & Santhanam, R., 24 Feb 2012, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France. p. 519-530 12 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Open Access
    File