NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
From MaRDI portal
Publication:3010398
DOI10.1007/978-3-642-20877-5_17zbMath1331.68086OpenAlexW1535289693MaRDI QIDQ3010398
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_17
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (4)
Nonuniform ACC Circuit Lower Bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Depth Reduction for Composites ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- On ACC
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Robust simulations and significant separations
- Improving exhaustive search implies superpolynomial lower bounds
- A Uniform Circuit Lower Bound for the Permanent
- Optimal bounds for decision problems on the CRCW PRAM
- Computational Complexity
This page was built for publication: NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
