Perceptrons, PP, and the polynomial hierarchy

DOI10.1007/BF01263422zbMath0829.68059OpenAlexW2150157290MaRDI QIDQ1346615

Richard Beigel

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

zbMATH Keywords

perceptron

Mathematics Subject Classification ID

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

Related Items (32)

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

This page was built for publication: Perceptrons, PP, and the polynomial hierarchy