✦ LIBER ✦

Bounded-depth, polynomial-size circuits for symmetric functions

✍ Scribed by Ronald Fagin; Maria M. Klawe; Nicholas J. Pippenger; Larry Stockmeyer

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 787 KB
Volume: 36
Category: Article
ISSN: 0304-3975
DOI: 10.1016/0304-3975(85)90045-3

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Optimal lower bounds on the depth of pol

Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions

✍ Ingo Wegener 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 176 KB

Threshold functions and bounded depth mo

Threshold functions and bounded depth monotone circuits

✍ Ravi B. Boppana 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 494 KB

The circuit depth of symmetric boolean f

The circuit depth of symmetric boolean functions

✍ William F. McColl 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 354 KB

Lower bounds for constant-depth circuits

Lower bounds for constant-depth circuits in the presence of help bits

✍ Jin-yi Cai 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 435 KB

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 size-depth trade-off for the analog co

A size-depth trade-off for the analog computation of Boolean functions

✍ György Turán; Farrokh Vatan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 399 KB