Recent Advances in Arithmetic Circuit Lower Bounds

Опубликовано 8 августа 2016, 22:54

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.