Algorithms and Complexity Seminar
The role of pseudorandomness in the testing of boolean functions
Victor Chen (MIT)
In this talk, I shall focus on the testability of Boolean functions f:{0,1}^n->{0,1} and discuss the application of the framework in additive combinatorics (using the concept of Gowers uniformity norms) to the analysis of several testing algorithms.
Two applications will be described. While they are seemingly different, the theme lies in the Ramsey-like behavior of the algorithms, i.e., whenever a function is far from having a property, many sequences of queries must cause the algorithm to reject. With an appropriate consideration of "pseudorandomness" for functions, one can apply analytical tools to analyze the behavior of these algorithms when a function is far from having the specified property.
The first is concerned with the tradeoff between the number of queries a testing algorithm makes and its error probability in the context of PCPs. Specifically the focus is on dictatorship testing (f(x)=x_i for some i), an important component in PCP construction. Building on the work of Samorodnitsky and Trevisan, who achieved a dictatorship test with amortized query complexity 1+O(log q/q) (where q is the number of queries) but has imperfect completeness, a new dictatorship test achieving both perfect completeness and the same amortized query complexity is obtained.
The second, joint with A. Bhattacharyya, M. Sudan, N. Xie, is concerned with the number of "patterns" in a function. The classical BLR linearity test over {0,1}^n deals with the number of triplets (f(x),f(y),f(x+y)) that contains an odd number of 1s. Within a different context, Green shows that the property of a function being "triangle-free" is testable, where a function is triangle-free if it has no triplet (f(x),f(y),f(x+y)) that are all 1s. We extend Green's result to show that for any graph the property of "graph-free" is testable.