✦ LIBER ✦

Top-down lower bounds for depth-three circuits

✍ Scribed by J. Håstad; S. Jukna; P. Pudlák

Publisher: Springer
Year: 1995
Tongue: English
Weight: 754 KB
Volume: 5
Category: Article
ISSN: 1016-3328
DOI: 10.1007/bf01268140

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Exponential lower bounds for depth three

Exponential lower bounds for depth three Boolean circuits

✍ R. Paturi; M. E. Saks; F. Zane 📂 Article 📅 2000 🏛 Springer 🌐 English ⚖ 274 KB

Lower Bounds and Separations for Constan

Lower Bounds and Separations for Constant Depth Multilinear Circuits

✍ Ran Raz; Amir Yehudayoff 📂 Article 📅 2009 🏛 Springer 🌐 English ⚖ 663 KB

A tight lower bound for top-down skew he

A tight lower bound for top-down skew heaps

✍ Berry Schoenmakers 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 498 KB

Previously, it was shown in a paper by Kaldewaij and Schoenmakers that for top-down skew heaps the amortized number of comparisons required for meld and delmin is upper bounded by log+ R, where n is the total size of the inputs to these operations and r#~ = (& + 1) /2 denotes the golden ratio. In th

Communication complexity towards lower b

Communication complexity towards lower bounds on circuit depth

✍ J. Edmonds; R. Impagliazzo; S. Rudich; J. Sgall 📂 Article 📅 2001 🏛 Springer 🌐 English ⚖ 543 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

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