Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
From MaRDI portal
Publication:685431
DOI10.1016/0304-3975(93)90214-EzbMath0783.68047OpenAlexW2081131534MaRDI QIDQ685431
Publication date: 17 October 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(93)90214-e
Boolean functionpolynomial-time hierarchydepth-three deterministic circuitsdepth-two probabilistic circuitsrandomized many-one polynomial-time reduction
Related Items
When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one, Perceptrons, PP, and the polynomial hierarchy, On ACC, Representing Boolean functions as polynomials modulo composite numbers, Uniform proofs of ACC representations, Algebraic methods and bounded formulas, On closure properties of bounded two-sided error complexity classes, On the probabilistic degree of OR over the reals, Paradigms for Unconditional Pseudorandom Generators, Learning $$AC^0$$ Under k-Dependent Distributions, On polynomial approximations to AC, Learning Complexity vs Communication Complexity, Quantum and classical complexity classes: Separations, collapses, and closure properties, Symmetric polynomials over \(\mathbb Z_{m}\) and simultaneous communication protocols, Unnamed Item, On the Probabilistic Degrees of Symmetric Boolean Functions, Depth Reduction for Circuits with a Single Layer of Modular Counting Gates, Derandomizing Isolation in Space-Bounded Settings, Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Relations among MOD-classes
- NP is as easy as detecting unique solutions
- The complexity of combinatorial problems with succinct input representation
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The polynomial-time hierarchy
- Probabilistic complexity classes and lowness
- A circuit-based proof of Toda's theorem
- Rational approximation to \(|x|\)
- Parity, circuits, and the polynomial-time hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Alternation
- On the power of deterministic reductions to C=P
- Computational Complexity of Probabilistic Turing Machines
- On the power of parity polynomial time
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Counting classes: Thresholds, parity, mods, and fewness
