✦ LIBER ✦

Lower bounds on monotone arithmetic circuits with restricted depths

✍ Scribed by Joseph JáJá

Book ID: 108020136
Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 568 KB
Volume: 11
Category: Article
ISSN: 0898-1221
DOI: 10.1016/0898-1221(85)90103-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Lower Bounds on the Depth of Monotone Ar

Lower Bounds on the Depth of Monotone Arithmetic Computations

✍ Don Coppersmith; Baruch Schieber 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 128 KB

dedicated to zvi galil's 50th birthday Consider an arithmetic expression of length n involving only the operations [+, \_] and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We

Lower bounds on arithmetic circuits via

Lower bounds on arithmetic circuits via partial derivatives

✍ Noam Nisan; Avi Wigderson 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 883 KB

A lower bound for monotone arithmetic ci

A lower bound for monotone arithmetic circuits computing 0–1 permanent

✍ Rimli Sengupta; H. Venkateswaran 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 621 KB

A direct version of Shamir and Snir's lo

A direct version of Shamir and Snir's lower bounds on monotone circuit depth

✍ Prasoon Tiwari; Martin Tompa 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 512 KB

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

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