DocumentCode
2454887
Title
Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP
Author
Vereshchagin, Nikolai K.
Author_Institution
Dept. of Math. Logic, Moscow State Univ., Russia
fYear
1995
fDate
4-6 Jan 1995
Firstpage
46
Lastpage
51
Abstract
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∩co-AM⊄≠PP under some oracle. This contrasts the fact that MA⊆PP under any oracle
Keywords
Boolean algebra; automata theory; matrix algebra; perceptrons; threshold logic; Boolean matrices; oracle; oracle separation; perceptrons; separation problems; Boolean functions; Circuits; Complexity theory; Cultural differences; Functional analysis; Linear programming; Polynomials; Turing machines; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Theory of Computing and Systems, 1995. Proceedings., Third Israel Symposium on the
Conference_Location
Tel Aviv
Print_ISBN
0-8186-6915-2
Type
conf
DOI
10.1109/ISTCS.1995.377047
Filename
377047
Link To Document