Eric Blais

Testing Properties of Boolean Functions Degree Type: Ph.D. in Computer Science
Advisor(s): Ryan O'Donnell
Graduated: May 2012

Abstract:

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 k variables) and k-linearity (functions that return the parity of exactly k of the input bits). These two problems are fundamental in the study of boolean functions and the bounds obtained for these two properties lead to tight or improved bounds on the query complexity for testing many other properties including, for example, testing sparse polynomials, testing low Fourier degree, and testing computability by small-size decision trees.

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.

Thesis Committee:
Ryan O’Donnell (Chair)
Avrim Blum
Venkatesan Guruswami
Ronitt Rubinfeld (M.I.T.)
Madhu Sudan (Microsoft Research)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Property Testing, Boolean Functions, Juntas, Partial Symmetry, Linear Functions, Function Isomorphism, Communication Complexity, Learning Theory, Decision Tree Complexity