✦ LIBER ✦

A lower bound for the hitting set size for combinatorial rectangles and an application

✍ Scribed by L.Sunil Chandran

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 87 KB
Volume: 86
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00475-1

No coin nor oath required. For personal study only.

✦ Synopsis

We prove a lower bound of ( 1 ε (m + log(da)) where a = log m ( 1 4ε ) for the hitting set size for combinatorial rectangles of volume at least ε in

9 ] and d > 2.

📜 SIMILAR VOLUMES

An Upper and a Lower Bound Theorem for C

An Upper and a Lower Bound Theorem for Combinatorial 4-Manifolds

✍ E. Sparla 📂 Article 📅 1998 🏛 Springer 🌐 English ⚖ 222 KB

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

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

An efficient lower bound for the general

An efficient lower bound for the generalized spectral radius of a set of matrices

✍ Mohsen Maesumi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 427 KB

A Lower Bound for the CenteredL2-Discrep

A Lower Bound for the CenteredL2-Discrepancy on Asymmetric Factorials and its Application

✍ Kashinath Chatterjee; Kai-Tai Fang; Hong Qin 📂 Article 📅 2005 🏛 Springer 🌐 English ⚖ 159 KB

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