Functions that have read‐twice constant width branching programs are not necessarily testable
Eldar Fischer, Ilan Newman, Jiřı́ Sgall · Random Structures and Algorithms · 2004
Abstract We construct a property on 0/1‐strings that has a representation by a collection of width‐3 read‐twice oblivious branching programs, but for which any two‐sided ϵ‐testing algorithm must query at least Ω(nδ) many queries for some fixed ϵ and δ. This shows that Newman's result [Testing of functions that have small width branching programs, SIAM J Comput 31 (2002), 1557–1570] cannot be generalized to read‐k‐times functions fork> 1. In addition, we exhibit a property that has also a representation by a CNF formula of constant clause size. Hence, the nontestability results extend to properties that in addition have small (constant size) 0‐witnesses. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004