✦ LIBER ✦

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

✍ Scribed by Raz, Ran; Shpilka, Amir; Yehudayoff, Amir

Book ID: 118180919
Publisher: Society for Industrial and Applied Mathematics
Year: 2008
Tongue: English
Weight: 330 KB
Volume: 38
Category: Article
ISSN: 0097-5397
DOI: 10.1137/070707932

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

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

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

Exponential Lower Bounds for Depth 3 Ari

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields

✍ D. Grigoriev; A. Razborov 📂 Article 📅 2000 🏛 Springer 🌐 English ⚖ 184 KB

Lower bounds on the size of bounded dept

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

✍ A. A. Razborov 📂 Article 📅 1987 🏛 SP MAIK Nauka/Interperiodica 🌐 English ⚖ 432 KB

A Lower Bound for the Formula Size of Ra

A Lower Bound for the Formula Size of Rational Functions

✍ Kalorkoti, K. A. 📂 Article 📅 1985 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 882 KB