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

A perception is a circuit with a single threshold gate, whose inputs are the outputs of boolean circuits with AND, OR, and NOT gates at the top, called the perceptron's subcircuits. The author shows that there are functions computable by linear size boolean circuits of depth \(k\) that require superpolynomial size perceptrons of depth \(k- 1,\) for \(k<\log n/(6 \log \log n)\) and exponential size perceptrons for constant \(k.\) The key to making the proof work is to use a separation between polynomial size depth-2 perceptrons with bounded fan-in and general polynomial size depth-2 perceptrons as the basis for the induction. This result implies the existence of an oracle \(A\) such that \(\Sigma_k^{p, A}\nsubseteq \text{PP}^{\Sigma_{k-2}^{p,A}}\) and, in particular, this oracle separates the levels in the \(\text{PP}^{\text{PH}}\) hierarchy. Using the same ideas, it is shown a lower bound for another function, which makes it possible to get an oracle \(A\) such that \(\Delta_k^{p,A}\nsubseteq \text{PP}^{\Sigma_{k-2}^{p,A}}.\)