Uniform proofs of ACC representations
From MaRDI portal
Publication:2402964
DOI10.1007/s00153-017-0560-9zbMath1406.03053OpenAlexW2617242237WikidataQ113906148 ScholiaQ113906148MaRDI QIDQ2402964
Publication date: 15 September 2017
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-017-0560-9
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- BPP and the polynomial hierarchy
- NP is as easy as detecting unique solutions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- On uniform circuit complexity
- Probabilistic complexity classes and lowness
- Depth reduction for circuits of unbounded fan-in
- On ACC
- The power of the middle bit of a \(\#\)P function
- A circuit-based proof of Toda's theorem
- A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Approximate counting by hashing in bounded arithmetic
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- A Uniform Circuit Lower Bound for the Permanent
- Computational Complexity
- Approximate counting in bounded arithmetic
