Lower bounds for bounded depth arithmetic circuits

Tuesday, September 9, 2014 - 4:15pm to 5:15pm

Refreshments:

3:45p Room G449

Location:

G449 (Patil/Kiva)

Speaker:

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.