ملخص: 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.

لغة: إنجليزية