✦ LIBER ✦

A lower bound for integer multiplication on randomized ordered read-once branching programs

✍ Scribed by Farid Ablayev; Marek Karpinski

Book ID: 114273400
Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 133 KB
Volume: 186
Category: Article
ISSN: 0890-5401
DOI: 10.1016/s0890-5401(03)00118-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Lower Bound for Integer Multiplication

A Lower Bound for Integer Multiplication with Read-Once Branching Programs

✍ Ponzio, Stephen 📂 Article 📅 1998 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 458 KB

Parity graph-driven read-once branching

Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication

✍ Beate Bollig; Stephan Waack; Philipp Woelfel 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 276 KB

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

A Lower Bound Technique for Nondetermini

A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications

✍ Beate Bollig; Philipp Woelfel 📂 Article 📅 2004 🏛 Springer 🌐 English ⚖ 232 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