Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth

Maurice Jansen, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We show that over fields of characteristic zero there does not exist a polynomial p ( n ) and a constant-free 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 black-box 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 languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I
EditorsLuca Aceto, Monika Henzinger, Jirí Sgall
PublisherSpringer-Verlag GmbH
Pages724-735
Number of pages12
ISBN (Print)978-3-642-22005-0
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume6755
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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.

Cite this