๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Christer Berg; Staffan Ulfberg

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
397 KB
Volume
56
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

We show 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). This result implies the existence of an oracle A such that 7 p, A k 3 PP 7 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 2 p, A k 3 PP 7 p, A k & 2 .

๐Ÿ“œ SIMILAR VOLUMES

An Exponential Lower Bound for the Size
An Exponential Lower Bound for the Size of Monotone Real Circuits
โœ Armin Haken; Stephen A. Cook ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed t

Upper and lower bounds on the drag coeff
Upper and lower bounds on the drag coefficient of a sphere in an Ellis model fluid
โœ Scott W. Hopke; John C. Slattery ๐Ÿ“‚ Article ๐Ÿ“… 1970 ๐Ÿ› American Institute of Chemical Engineers ๐ŸŒ English โš– 562 KB

Hill's extremum principles are not directly applicable to an Ellis model fluid. A method of adapting Hill's principles to the Ellis model was developed and used to calculate upper and lower bounds on the drag coefficient for a sphere moving slowly through such a fluid. Amilable experimental data wer

A superlinear lower bound for the size o
A superlinear lower bound for the size of a critical set in a latin square
โœ Nicholas J. Cavenagh ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 157 KB ๐Ÿ‘ 1 views

## Abstract A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. Let __scs__(__n__) denote the smallest possible size of a critical set in a latin square of order __n__. We show that for all __n__, $scs(n)\geq n\lfloo

A new lower bound for the critical proba
A new lower bound for the critical probability of site percolation on the square lattice
โœ J. van den Berg; A. Ermakov ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 705 KB

The critical probability for site percolation on the square lattice is not known exactly. Several authors have given rigorous upper and lower bounds. Some recent lower bounds are (each displayed here with the first three digits) 0.503 (Toth [13]), 0.522 (Zuev [15]), and the best lower bound so far,