Perceptrons, PP, and the polynomial hierarchy
From MaRDI portal
Publication:1346615
DOI10.1007/BF01263422zbMath0829.68059OpenAlexW2150157290MaRDI QIDQ1346615
Publication date: 6 April 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01263422
Related Items
Weights of exact threshold functions, Immunity and Simplicity for Exact Counting and Other Counting Classes, Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Approximate Degree in Classical and Quantum Computing, Breaking the Minsky--Papert Barrier for Constant-Depth Circuits, A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length, Improved approximation of linear threshold functions, A Short List of Equalities Induces Large Sign-Rank, Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\), A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$, Unnamed Item, Unbounded-error quantum query complexity, New degree bounds for polynomial threshold functions, The hardest halfspace, Extremal properties of polynomial threshold functions, Quantum computing, postselection, and probabilistic polynomial-time, LWPP and WPP are not uniformly gap-definable, Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, Complexity classes of equivalence problems revisited, Error-bounded probabilistic computations between MA and AM, Degree-uniform lower bound on the weights of polynomials with given sign function, Polynomial threshold functions and Boolean threshold circuits, Perceptrons of large weight, A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy, Relating polynomial time to constant depth, Unnamed Item, Unnamed Item, Unnamed Item, A note on the circuit complexity of PP, Dual lower bounds for approximate degree and Markov-Bernstein inequalities, On separation between the degree of a Boolean function and the block sensitivity
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
- Probabilistic polynomial time is closed under parity reductions
- On truth-table reducibility to SAT
- The expressive power of voting polynomials
- Depth reduction for circuits of unbounded fan-in
- On ACC
- PP is closed under intersection
- Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)
- Parity, circuits, and the polynomial-time hierarchy
- PP is as Hard as the Polynomial-Time Hierarchy
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- SeparatingPH fromPP by relativization
- A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
