On ACC
From MaRDI portal
Publication:1346616
DOI10.1007/BF01263423zbMath0835.68040MaRDI QIDQ1346616
Publication date: 6 April 1995
Published in: Computational Complexity (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
On learning embedded midbit functions, Entropy of operators or why matrix multiplication is hard for depth-two circuits, Threshold circuits of small majority-depth, When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one, Perceptrons, PP, and the polynomial hierarchy, Upper and lower bounds for some depth-3 circuit classes, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Efficient threshold circuits for power series, The correlation between parity and quadratic polynomials mod \(3\), Algorithms for modular counting of roots of multivariate polynomials, Depth Reduction for Circuits with a Single Layer of Modular Counting Gates, Quantum multiparty communication complexity and circuit lower bounds, An Algebraic Perspective on Boolean Function Learning
Cites Work
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Depth reduction for circuits of unbounded fan-in
- PP is closed under intersection
- A circuit-based proof of Toda's theorem
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- PP is as Hard as the Polynomial-Time Hierarchy
- Finite monoids and the fine structure of NC 1
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Counting classes: Thresholds, parity, mods, and fewness
- Unnamed Item
