✦ LIBER ✦

A simple function that requires exponential size read-once branching programs

✍ Scribed by Anna Gál

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 349 KB
Volume: 62
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00041-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A very simple function that requires exp

A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

✍ Beate Bollig 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 105 KB

Functions that have read-once branching

Functions that have read-once branching programs of quadratic size are not necessarily testable

✍ Beate Bollig; Ingo Wegener 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 89 KB

A property of binary strings is constructed that has a representation by a collection of read-once branching programs of quadratic size but which is not ε-testable for some fixed ε > 0. This shows that Newman's result [Proc. 41st FOCS, 2000, pp. 251-258] cannot be generalized to functions representa