Functions that have read-once branching programs of quadratic size are not necessarily testable
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 E-testable for some fixed epsilon > 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. (C) 2003 Elsevier Science B.V. All rights reserved.
branching programs computational complexity binary decision diagrams property testing