Fourier methods and combinatorics in learning theory

In this thesis we study computational learning theory. Our main problem is the following: given an unknown function f : X → {0, 1} and some sort of oracle access to f, can we construct a function "close" to f? We are concerned primarily with two perspectives: making use of orthogonal decompositions and learning theory conjectures that naturally lead to combinatorics results.;With relation to the former topic, we attempt to generalize beyond the most commonly studied PAC-learning model: learning from independent labeled random examples over the uniform distribution. We make two contributions in this way: (1) We study the problem of learning from random walks. Specifically, we give a quasi-polynomial for learning the class of "threshold-of-parities" under the uniform distribution from random walks. Further, we generalize known results about learning DNF expressions and agnostically learning juntas into more general random walk models. (2) We study learning from independent labeled random examples over arbitrary product distributions. We show that essentially every result about learning boolean functions over the uniform distribution on the boolean cube via Fourier methods can be transferred to any product distribution. The crux of the method is a very simple but powerful proof relating the noise sensitivity of a function under the uniform distribution to its noise sensitivity under any product distribution.;Also, we make two contributions to combinatorics, both related to the Kruskal-Katona Theorem: (1) Using the Kruskal-Katona Theorem from extremal combinatorics, we show that any monotone boolean function "close" to the majority function has large total influence, and thus requires an exponential-size circuit to compute it for any constant depth. The motivation is a conjecture of Benjamini, Kalai, and Schramm, which we ultimately disprove with an explicit counterexample. (2) We extend the celebrated Kahn-Kalai-Linial Theorem to more general settings; we eliminate the seeming dependence on product distributions. Using this theorem in an appropriate scenario, we prove a stability version of the Kruskal-Katona Theorem. Finally, equipped with this theorem, we prove a conjecture of Blum, Burch, and Langford on learning monotone functions.