✦ LIBER ✦

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

✍ Scribed by Beate Bollig; Ingo Wegener

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 89 KB
Volume: 87
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(03)00230-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 representable by read-once branching programs of polynomial size.