A Uniform Circuit Lower Bound for the Permanent

DOI10.1137/S0097539792233907zbMath0813.68097DBLPjournals/siamcomp/AllenderG94OpenAlexW2069864904WikidataQ56806473 ScholiaQ56806473MaRDI QIDQ4312420

Eric W. Allender, Vivek K. Gore

Publication date: 29 November 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792233907

zbMATH Keywords

circuit complexitynonuniform ACC circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Uniform proofs of ACC representations ⋮ Dual VP classes ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ MONOIDS AND COMPUTATIONS ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Nondeterministic \(NC^1\) computation ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unifying known lower bounds via geometric complexity theory

This page was built for publication: A Uniform Circuit Lower Bound for the Permanent