A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy

DOI10.1006/jcss.1997.1552zbMath0912.68001OpenAlexW2175992284MaRDI QIDQ1271610

Staffan Ulfberg, Christer Berg

Publication date: 25 March 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1552

zbMATH Keywords

circuit complexityrelativizationperceptionparityboolean circuitspolynomial time hierarchylower bound for perceptronsmathematical problems of computer architectureoracle separation

Mathematics Subject Classification ID

Mathematical problems of computer architecture (68M07)

Related Items (1)

Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)

Cites Work

• Unnamed Item
• On the power of small-depth threshold circuits
• Probabilistic polynomial time is closed under parity reductions
• An oracle separating \(\oplus P\) from \(PP^{PH}\)
• Perceptrons, PP, and the polynomial hierarchy
• PP is closed under intersection
• Parity, circuits, and the polynomial-time hierarchy
• SeparatingPH fromPP by relativization
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• A lower bound for monotone perceptrons

This page was built for publication: A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy