𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Exponential Lower Bound for the Size of Monotone Real Circuits

✍ Scribed by Armin Haken; Stephen A. Cook

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
118 KB
Volume
58
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 to compute arbitrary monotone binary real-valued functions (including AND and OR). Our proof is relatively simple and direct and uses the method of counting bottlenecks. The generalization was proved independently by Pudla k using a different method, who also showed that the result can be used to obtain an exponential lower bound on the size of unrestricted cutting plane proofs in the propositional calculus.

πŸ“œ SIMILAR VOLUMES

New lower bounds for the size of edge ch
New lower bounds for the size of edge chromatic critical graphs
✍ Yue Zhao πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 108 KB πŸ‘ 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Ξ”. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004

An Absolute Bound for the Size of Diopha
An Absolute Bound for the Size of Diophantine m-Tuples
✍ Andrej Dujella πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 178 KB

A set of m positive integers is called a Diophantine m-tuple if the product of its any two distinct elements increased by 1 is a perfect square. We prove that if [a, b, c] is a Diophantine triple such that b>4a and c>max[b 13 , 10 20 ] or c>max[b 5 , 10 1029 ], then there is unique positive integer

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 Lower Bound for Perceptrons and an Ora
A Lower Bound for Perceptrons and an Oracle Separation of the PPPHHierarchy
✍ Christer Berg; Staffan Ulfberg πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 397 KB

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 separate