CMU-CS-12-101Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-12-101
Eric Blais January 2012 Ph.D. Thesis
Keywords: Property Testing, Boolean Functions, Juntas, Partial
Symmetry, Linear Functions, Function Isomorphism, Communication Complexity,
Learning Theory, Decision Tree Complexity
Given oracle access to some boolean function f, how many queries do we need to test whether f is linear? Or monotone? Or whether its output is completely determined by a small number of the input variables? This thesis studies these and related questions in the framework of property testing introduced by Rubinfeld and Sudan ('96). The results of this thesis are grouped into three main lines of research.
I. We determine nearly optimal bounds on the number of queries required
to test k-juntas (functions that depend on at most II. We give a partial characterization of the set of functions for which we can test isomorphism–that is, identity up to permutation of the labels of the variables–with a constant number of queries. This result provides some progress on the question of characterizing the set of properties of boolean functions that can be tested with a constant number of queries. III. We establish new connections between property testing and other areas of computer science. First, we present a new reduction between testing problems and communication problems. We use this reduction to obtain many new lower bounds in property testing from known results in communication complexity. Second, we introduce a new model of property testing that closely mirrors the active learning model. We show how testing results in this new model may be used to improve the efficiency of model selection algorithms in learning theory. The results presented in this thesis are obtained by applying tools from various mathematical areas, including probability theory, the analysis of boolean functions, orthogonal polynomials, and extremal combinatorics. 162 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |