Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy

DOI10.1016/0304-3975(93)90214-EzbMath0783.68047OpenAlexW2081131534MaRDI QIDQ685431

Jun Tarui

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

zbMATH Keywords

Boolean functionpolynomial-time hierarchydepth-three deterministic circuitsdepth-two probabilistic circuitsrandomized many-one polynomial-time reduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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