Uniform proofs of ACC representations

DOI10.1007/S00153-017-0560-9MaRDI QIDQ2402964zbMATH OpenOpenAlexWikidataFDO

Authors Samuel R. Buss

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

zbMATH Keywords

constant depth circuitsmodular countingToda theoremuniform circuitsBeigel-Tarui theorem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• On ACC
• Some results on uniform arithmetic circuit complexity
• A Uniform Circuit Lower Bound for the Permanent
• A note on some languages in uniform \(ACC^ 0\)
• scientific article; zbMATH DE number 1559592

Cites work

• scientific article; zbMATH DE number 1301088 (Why is no real title available?)
• scientific article; zbMATH DE number 1351078 (Why is no real title available?)
• scientific article; zbMATH DE number 1114025 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• A Uniform Circuit Lower Bound for the Permanent
• A circuit-based proof of Toda's theorem
• A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
• A note on \(\mathbf{MOD}_{p}\)-\(\mathbf{MOD}_{m}\) circuits
• A simple proof of Toda's theorem
• Approximate counting by hashing in bounded arithmetic
• Approximate counting in bounded arithmetic
• BPP and the polynomial hierarchy
• Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
• Computational Complexity
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Depth reduction for circuits of unbounded fan-in
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• NP is as easy as detecting unique solutions
• On ACC
• On uniform circuit complexity
• PP is as Hard as the Polynomial-Time Hierarchy
• Parity, circuits, and the polynomial-time hierarchy
• Probabilistic complexity classes and lowness
• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• The power of the middle bit of a \(\#\)P function

Cited in

(2)

• A note on uniform circuit lower bounds for the counting hierarchy (extended abstract)
• Risk management of supply chain disruptions: an epidemic modeling approach

This page was built for publication: Uniform proofs of ACC representations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402964)