Recent Advances in Arithmetic Circuit Lower Bounds

  • Ramprasad Saptharishi | Chennai Mathematical Institute

Arithmetic circuits provide a robust measure of understanding the hardness of polynomials. The most important open problem in this field is to separate the complexities of the `Determinant’ and `Permanent’ families; this was also formalized by an arithmetic version of the “P vs NP” problem by Valiant.

The task of proving lower bounds has always been daunting. However, there has been a lot of progress in the last year that has greatly increased our optimism that the task of proving arithmetic circuit lower bounds may not be that far away from our reach. Jointly with Ankit Gupta, Pritish Kamath and Neeraj Kayal (CCC 2013), we presented a new technique that takes us tantalizingly close to our goal. In this talk, I shall describe this lower bound in reasonable detail, and also briefly present some subsequent work.

Speaker Details

I am Ramprasad Saptharishi, and I just defended my Ph.D thesis in Theoretical Computer Science at Chennai Mathematical Institute. My advisor for my Ph.D was Dr Manindra Agrawal at the Indian Institute of Technology, Kanpur. I am currently on the lookout for postdocs.

My academic interests are

1.Pseudorandomness and derandomization

2.Arithmetic circuit complexity

Watch Next