On ACC
From MaRDI portal
Publication:1346616
DOI10.1007/BF01263423zbMath0835.68040OpenAlexW2912133662MaRDI QIDQ1346616
Publication date: 6 April 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01263423
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (41)
The correlation between parity and quadratic polynomials mod \(3\) ⋮ Hellinger volume and number-on-the-forehead communication complexity ⋮ Local Reductions ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ Local reduction ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Uniform proofs of ACC representations ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ Hadamard tensors and lower bounds on multiparty communication complexity ⋮ The function-inversion problem: barriers and opportunities ⋮ Dual VP classes ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Unnamed Item ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Depth Reduction for Composites ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ The NOF multiparty communication complexity of composed functions ⋮ NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth ⋮ Degree lower bounds of tower-type for approximating formulas with parity quantifiers ⋮ One-way multiparty communication lower bound for pointer jumping with applications ⋮ Algorithms for modular counting of roots of multivariate polynomials ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ Quantum multiparty communication complexity and circuit lower bounds ⋮ Natural Proofs versus Derandomization ⋮ Unnamed Item ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Threshold circuits of small majority-depth ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ An Algebraic Perspective on Boolean Function Learning ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Efficient threshold circuits for power series ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ On learning embedded midbit functions
Cites Work
- Unnamed Item
- 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
This page was built for publication: On ACC
