The Gowers norm in the testing of Boolean functions
Victor Yen-Wen Chen · 2009
A property tester is a fast, randomized algorithm that reads only a few entries of the input, and based on the values of these entries, it distinguishes whether the input has a certain property or is “different ” from any input having this property. Furthermore, we say that a property tester has completeness c and soundness s if it accepts all inputs having the property with probability at least c and accepts “different ” inputs with probability at most s+ o(1). In this thesis we present two property testers for boolean functions on the boolean cube {0, 1}n. We summarize our contribution as follows. • We present a new dictatorship test that determines whether the function is a dictator (of the form f(x) = xi for some coordinate i), or a function that is an “anti-dictator. ” Our test is “adaptive, ” makes q queries, has completeness 1, and soundness O(q3) · 2−q. Previously, a dictatorship test that has sound-