A Lower Bound for Perceptrons and an Oracle Separation of the PPPHHierarchy

摘要

We show that there are functions computable by linear size boolean circuits of depthkthat require superpolynomial size perceptrons of depthk−1, fork