A new characterization of ACC^0 and probabilistic CC^0

DOI10.1007/S00037-010-0287-ZMaRDI QIDQ626674zbMATH OpenOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen, Michal Koucký

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-010-0287-z

zbMATH Keywords

AND functionBoolean circuitsbranching programsmodular countingplanarityprobabilistic circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
• STACS 2004
• Constant width planar computation characterizes ACC\(^{0}\)
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On ACC

Cited in

(10)

• Uniform proofs of ACC representations
• Dual VP classes
• Constant width planar computation characterizes ACC\(^{0}\)
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of o( n) depth
• scientific article; zbMATH DE number 1129497 (Why is no real title available?)
• CC-circuits and the expressive power of nilpotent algebras
• STACS 2004
• Complexity of modular circuits
• Hardness of equations over finite solvable groups under the exponential time hypothesis
• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)

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