Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP
Nikolay Vereshchagin · 2002
We prove that perceptrons separating Boolean matrices in which each row has a one from matrices in which many rows have no one must have either large total weight or large order. This result extends one-in-a-box theorem by Minsky and Papert (1988) stating that perceptrons of small order cannot decide if each row of a given Boolean matrix has a one. As a consequence, we prove that AM/spl cap/co-AM/spl nsub//spl ne/PP under some oracle. This contrasts the fact that MA/spl sube/PP under any oracle.>