A LOWER-BOUND FOR PERCEPTRONS AND AN ORACLE SEPARATION OF THE PPPH HIERARCHY

Authors
BERG C ULFBERG S
Citation
C. Berg et S. Ulfberg, A LOWER-BOUND FOR PERCEPTRONS AND AN ORACLE SEPARATION OF THE PPPH HIERARCHY, Journal of computer and system sciences (Print), 56(3), 1998, pp. 263-271
Citations number
14
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Hardware & Architecture","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences (Print) → ACNP
ISSN journal
00220000
Volume
56
Issue
3
Year of publication
1998
Pages
263 - 271
Database
ISI
SICI code
0022-0000(1998)56:3<263:ALFPAA>2.0.ZU;2-5
Abstract
We show that there are functions computable by linear size boolean cir cuits of depth k that require superpolynomial size perceptrons of dept h k - 1, for k < log n/(6 log log n). This result implies the existenc e of an oracle A such that Sigma(k)(p,A) not subset of or equal to PP (Sigma)(p,A)(k-2) and, in particular, this oracle separates the levels in the pp(PH) hierarchy. Using the same ideas, we show a lower bound for another function, which makes it possible to strengthen the oracle separation to Delta(k)(p,A) not subset of or equal to PPk-2Sigmap.A. 1998 Academic Press.