Premium
Functions that have read‐twice constant width branching programs are not necessarily testable
Author(s) -
Fischer Eldar,
Newman Ilan,
Sgall Jiří
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10110
Subject(s) - branching (polymer chemistry) , constant (computer programming) , mathematics , property (philosophy) , property testing , combinatorics , representation (politics) , struct , discrete mathematics , computer science , philosophy , materials science , epistemology , politics , political science , law , composite material , programming language
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 for k > 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