Title :
Recent Progress on Lower Bounds for Arithmetic Circuits
Author :
Saraf, Shubhangi
Author_Institution :
Dept. of Math. & Dept. of Comput. Sci., Rutgers Univ., Piscataway, NJ, USA
Abstract :
In recent years there has been much exciting progress on depth reduction of arithmetic circuits and lower bounds for bounded depth arithmetic circuits. We will survey some of these results and highlight some of the main challenges and open questions that remain.
Keywords :
computational complexity; bounded depth arithmetic circuits; depth reduction; lower bounds; Complexity theory; Computational modeling; Integrated circuit modeling; Logic gates; Polynomials; Testing; Upper bound; arithmetic circuits; depth reduction; lower bounds;
Conference_Titel :
Computational Complexity (CCC), 2014 IEEE 29th Conference on
Conference_Location :
Vancouver, BC
DOI :
10.1109/CCC.2014.23
