A Uniform Circuit Lower Bound for the Permanent
From MaRDI portal
Publication:4312420
DOI10.1137/S0097539792233907zbMath0813.68097WikidataQ56806473 ScholiaQ56806473MaRDI QIDQ4312420
Eric W. Allender, Vivek K. Gore
Publication date: 29 November 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Faster All-Pairs Shortest Paths via Circuit Complexity, MONOIDS AND COMPUTATIONS, Lower bounds against weakly-uniform threshold circuits, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Nondeterministic \(NC^1\) computation, Unifying known lower bounds via geometric complexity theory, Uniform proofs of ACC representations, Dual VP classes, $$P\mathop{ =}\limits^{?}NP$$, NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth