Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Recent Advances in Arithmetic Circuit Lower Bounds

Speaker  Ramprasad Saptharishi

Affiliation  Chennai Mathematical Institute

Host  Satya Lokam

Duration  00:55:57

Date recorded  28 July 2013

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.

©2013 Microsoft Corporation. All rights reserved.
> Recent Advances in Arithmetic Circuit Lower Bounds