𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Better Lower Bounds for Monotone Threshold Formulas

✍ Scribed by Jaikumar Radhakrishnan

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
670 KB
Volume
54
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We show that every monotone formula that computes the threshold function TH k, n , 2 k nΓ‚2, has size at least wkΓ‚2x n log(nΓ‚(k&1)). The same lower bound is shown to hold in the stronger monotone directed contact networks model.

πŸ“œ 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

A General Upper Bound for the Satisfiabi
A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
✍ O Dubois; Y Boufkhad πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 280 KB

Experiments on solving r-SAT random formulae have provided evidence of a satisfiability threshold phenomenon with respect to the ratio of the number of clauses to the number of variables of formulae. Presently, only the threshold of 2-SAT formulae has been proved to exist and has been computed to be