Permanent does not have succinct polynomial size arithmetic circuits of constant depth

DOI10.1016/j.ic.2012.10.013zbMath1272.68137OpenAlexW2105535257MaRDI QIDQ1951581

Maurice Jansen, Rahul Santhanam

Publication date: 6 June 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.10.013

zbMATH Keywords

lower boundspermanentarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)

Related Items (1)

Unifying known lower bounds via geometric complexity theory

This page was built for publication: Permanent does not have succinct polynomial size arithmetic circuits of constant depth