✦ LIBER ✦

A lower bound on branching programs reading some bits twice

✍ Scribed by Petr Savický; Stanislav Žák

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 625 KB
Volume: 172
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)00183-1

No coin nor oath required. For personal study only.

📜 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

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