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

Maurice Jansen; Rahul Santhanam

doi:10.1007/978-3-642-22006-7_61

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

Maurice Jansen
, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I
Editors	Luca Aceto, Monika Henzinger, Jirí Sgall
Publisher	Springer
Pages	724-735
Number of pages	12
ISBN (Print)	978-3-642-22005-0
DOIs	https://doi.org/10.1007/978-3-642-22006-7_61
Publication status	Published - 2011

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin / Heidelberg
Volume	6755
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-642-22006-7_61

http://link.springer.com/chapter/10.1007%2F978-3-642-22006-7_61

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R. (Principal Investigator)
EPSRC
1/10/10 → 31/12/12
Project: Research

Cite this

Jansen, M., & Santhanam, R. (2011). Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I (pp. 724-735). (Lecture Notes in Computer Science; Vol. 6755). Springer. https://doi.org/10.1007/978-3-642-22006-7_61

Jansen, Maurice ; Santhanam, Rahul. / Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. editor / Luca Aceto ; Monika Henzinger ; Jirí Sgall. Springer, 2011. pp. 724-735 (Lecture Notes in Computer Science).

@inproceedings{cbab70cc13bf4f23954a3b3bd9eb85e5,

title = "Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth",

abstract = "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.",

author = "Maurice Jansen and Rahul Santhanam",

year = "2011",

doi = "10.1007/978-3-642-22006-7\_61",

language = "English",

isbn = "978-3-642-22005-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "724--735",

editor = "Luca Aceto and Monika Henzinger and Jir{\'i} Sgall",

booktitle = "Automata, Languages and Programming",

address = "United Kingdom",

}

Jansen, M & Santhanam, R 2011, Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. in L Aceto, M Henzinger & J Sgall (eds), Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Lecture Notes in Computer Science, vol. 6755, Springer, pp. 724-735. https://doi.org/10.1007/978-3-642-22006-7_61

Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. / Jansen, Maurice; Santhanam, Rahul.
Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. ed. / Luca Aceto; Monika Henzinger; Jirí Sgall. Springer, 2011. p. 724-735 (Lecture Notes in Computer Science; Vol. 6755).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Jansen, Maurice

AU - Santhanam, Rahul

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-22006-7_61

DO - 10.1007/978-3-642-22006-7_61

M3 - Conference contribution

SN - 978-3-642-22005-0

T3 - Lecture Notes in Computer Science

SP - 724

EP - 735

BT - Automata, Languages and Programming

A2 - Aceto, Luca

A2 - Henzinger, Monika

A2 - Sgall, Jirí

PB - Springer

ER -

Jansen M, Santhanam R. Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. In Aceto L, Henzinger M, Sgall J, editors, Automata, Languages and Programming: 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I. Springer. 2011. p. 724-735. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-22006-7_61

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

Abstract

Publication series

Access to Document

Fingerprint

Projects

Hierarchies, Circuit Lower Bounds and Pseudorandomness

Cite this