✦ LIBER ✦

Superlinear Lower Bounds for Bounded-Width Branching Programs

✍ Scribed by D.A.M. Barrington; H. Straubing

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 635 KB
Volume: 50
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1995.1029

No coin nor oath required. For personal study only.

✦ Synopsis

We use algebraic techniques to obtain superlinear lower bounds on the size of bounded-width branching programs to solve a number of problems. In particular, we show that any bounded-width branching program computing a nonconstant threshold function has length (\Omega(n \log \log n)), improving on the previous lower bounds known to apply to all such threshold functions. We also show that any program over a finite solvable monoid computing a product in a nonsolvable group has length (\Omega(n \log \log n)). This result is a step toward proving the conjecture that the circuit complexity class (A C C^{\circ}) is properly contained in NC 1 . c 1995 Academic Press, Inc.

📜 SIMILAR VOLUMES

A lower bound for read-once-only branchi

A lower bound for read-once-only branching programs

✍ László Babai; Péter Hajnal; Endre Szemerédi; György Turán 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 582 KB

New Lower Bounds and Hierarchy Results f

New Lower Bounds and Hierarchy Results for Restricted Branching Programs

✍ Detlef Sieling 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

In unrestricted branching programs all variables may be tested arbitrarily often on each path. But exponential lower bounds are only known if on each path the number of tests of each variable is bounded. We examine branching programs in which for each path the number of variables that are tested mor

Lower bounds for monotone span programs

✍ Amos Beimel; Anna Gál; Mike Paterson 📂 Article 📅 1996 🏛 Springer 🌐 English ⚖ 900 KB

A lower bound on branching programs read

A lower bound on branching programs reading some bits twice

✍ Petr Savický; Stanislav Žák 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 625 KB

The power of nondeterminism in polynomia

The power of nondeterminism in polynomial- size bounded-width branching programs

✍ Christoph Meinel 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 717 KB

A read-once lower bound and a (1,+k)-hie

A read-once lower bound and a (1,+k)-hierarchy for branching programs

✍ P. Savický; S. Žák 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 143 KB

Branching programs (b. p.'s) or decision diagrams are a general graph-based model of sequential computation. The b. p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for di erent kinds of restricted b. p.'s are intensively investigated. An important restriction are the so-cal