A Uniform Circuit Lower Bound for the Permanent
From MaRDI portal
Publication:4312420
DOI10.1137/S0097539792233907zbMath0813.68097OpenAlexW2069864904WikidataQ56806473 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
Related Items
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