@inbook {19628,
title = {A Canonical Form for Testing Boolean Function Properties},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
series = {Lecture Notes in Computer Science},
year = {2011},
month = {2011/01/01/},
pages = {460 - 471},
publisher = {Springer Berlin Heidelberg},
organization = {Springer Berlin Heidelberg},
abstract = {In a well-known result Goldreich and Trevisan (2003) showed that every testable graph property has a {\textquotedblleft}canonical{\textquotedblright} tester in which a set of vertices is selected at random and the edges queried are the complete graph over the selected vertices. We define a similar-in-spirit canonical form for Boolean function testing algorithms, and show that under some mild conditions property testers for Boolean functions can be transformed into this canonical form. Our first main result shows, roughly speaking, that every {\textquotedblleft}nice{\textquotedblright} family of Boolean functions that has low noise sensitivity and is testable by an {\textquotedblleft}independent tester,{\textquotedblright} has a canonical testing algorithm. Our second main result is similar but holds instead for families of Boolean functions that are closed under ID-negative minors. Taken together, these two results cover almost all of the constant-query Boolean function testing algorithms that we know of in the literature, and show that all of these testing algorithms can be automatically converted into a canonical form.},
keywords = {Algorithm Analysis and Problem Complexity, Boolean functions, Computation by Abstract Devices, Computer Communication Networks, Computer Graphics, Data structures, Discrete Mathematics in Computer Science, property testing},
isbn = {978-3-642-22934-3, 978-3-642-22935-0},
url = {http://link.springer.com/chapter/10.1007/978-3-642-22935-0_39},
author = {Dana Dachman-Soled and Servedio, Rocco A.},
editor = {Goldberg, Leslie Ann and Jansen, Klaus and Ravi, R. and Rolim, Jos{\'e} D. P.}
}