Projects per year
Abstract / Description of output
We show that over fields of characteristic zero there does not exist a polynomial p ( n ) and a constantfree succinct arithmetic circuit family ? n , where ? n has size at most p ( n ) and depth O (1), such that ? n computes the n × n permanent. A circuit family ? n is succinct if there exists a nonuniform Boolean circuit family C n with O (log n ) many inputs and size n o (1) such that that C n can correctly answer direct connection language queries about ? n  succinctness is a relaxation of uniformity. To obtain this result we develop a novel technique that further strengthens the connection between blackbox derandomization of polynomial identity testing and lower bounds for arithmetic circuits. From this we obtain the lower bound by explicitly constructing a hitting set against arithmetic circuits in the polynomial hierarchy.
Original language  English 

Title of host publication  Automata, Languages and Programming 
Subtitle of host publication  38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 48, 2011, Proceedings, Part I 
Editors  Luca Aceto, Monika Henzinger, Jirí Sgall 
Publisher  SpringerVerlag GmbH 
Pages  724735 
Number of pages  12 
ISBN (Print)  9783642220050 
DOIs  
Publication status  Published  2011 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer Berlin / Heidelberg 
Volume  6755 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Fingerprint
Dive into the research topics of 'Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth'. Together they form a unique fingerprint.Projects
 1 Finished

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R.
1/10/10 → 31/12/12
Project: Research