enter search term and/or author name
Testing Read-Once Formula Satisfaction
Eldar Fischer, Yonatan Goldhirsh, Oded Lachish
Article No.: 5
We study the query complexity of testing for properties defined by read-once formulas, as instances of massively parametrized properties, and prove several testability and nontestability results. First, we prove the testability of any...
Tractable Parameterizations for the Minimum Linear Arrangement Problem
Michael R. Fellows, Danny Hermelin, Frances Rosamond, Hadas Shachnai
Article No.: 6
On Sample-Based Testers
Oded Goldreich, Dana Ron
Article No.: 7
The standard definition of property testing endows the tester with the ability to make arbitrary queries to “elements” of the tested object. In contrast, sample-based testers only obtain independently distributed elements (a.k.a....