𝔖 Bobbio Scriptorium
✦   LIBER   ✦

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

✍ Scribed by Rimli Sengupta; H. Venkateswaran

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
621 KB
Volume
209
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 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 lower bound for a constrained quadrati
A lower bound for a constrained quadratic 0–1 minimization problem
✍ Alain Billionnet; Alain Faye 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 659 KB

Given a quadratic pseudo-Boolean function f (x 1, . , XJ written as a multilinear polynomial in its variables, Hammer et al. [7] have studied, in their paper "Roof duality, complementation and persistency in quadratic 0-I optimization", the greatest constant c such that there exists a quadratic posi