Functions that have read‐twice constant width branching programs are not necessarily testable | Zendy

Fischer Eldar | Zendy; Newman Ilan | Zendy; Sgall Jiří | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research