Lower bounds for bounded depth arithmetic circuits

Tuesday, September 9, 2014 - 4:15pm to 5:15pm
3:45p Room G449
G449 (Patil/Kiva)
Shubhangi Saraf, Assistant Professor, Dept.of Mathematics and Dept. of Computer Science, Rutgers University
Abstract: In the last few years there have been several exciting results on depth reduction of arithmetic circuits and strong lower bounds for bounded depth arithmetic circuits. These lower bounds come very close to showing VP not equal to VNP (the algebraic analog of the P vs NP conjecture). I will survey these results, and highlight some of the main challenges and open directions in this area.