COMP 760 (Fall 2011): Harmonic Analysis of Boolean Functions

Instructor's contact: See Here

Lectures: MW 11:35-12:55 in McConnell Engineering Building 103 (Starting from tomorrow, Wednesday, the class is 11:35-12:55)

Office Hours: By appointment (hatami at cs mcgill ca)

Course description:

This course is intended for graduate students in theoretical computer science or mathematics. Its purpose is to study Boolean functions via Fourier analytic tools. This analytic approach plays an essential role in modern theoretical computer science and combinatorics (e.g. in circuit complexity, hardness of approximation, machine learning, communication complexity, graph theory), and it is the key to understanding many fundamental concepts such as pseudo-randomness.

During the past two decades there have been major developments in the interaction between harmonic analysis, discrete mathematics, theoretical computer science and combinatorial number theory. These advances have developed into an entire area called discrete harmonic analysis. In this course the emphasis will be on the part of the theory that's most relevant to the study of Boolean functions. However many of the ideas are not specific to this and can be applied to a wider range of problems, e.g. in additive combinatorics.

This course will equally focus on developing the area's basic mathematics, and on the applications in theoretical computer science and discrete mathematics.

Course Information

Prerequisites:

The main prerequisite is mathematical maturity and interest in some of the application fields (theoretical computer science, combinatorics, discrete probability, discrete harmonic analysis). The students must be comfortable with basic concepts of probability theory such as random variables, linearity of expectations, variance, conditional expectation, and with basic concepts of linear algebra such as orthonormal basis, inner products, linear transformations. However no background in harmonic analysis is required.

Lectures:

Lecture 0: Introduction to the course.
Lecture 1: Background: Basic inequalities, Basic Probability theory, Normed spaces. 19/09/11: Borel-Cantelli (Theorem 2.8) and Section 4 are now added.
Lectures 2-3: Fourier Analysis of Finite Abelian Groups. 14/09/11: Lecture 3 is also included now.
Lectures 4-5: Fourier Uniformity and Linearity Test.
Lectures 6-8: Fourier spectrum of functions with bounded depth circuits: Hastad's Switching lemma and [Linial, Mansour, Nisan], and [Razborov-Smolensky] 03/10/11: updated with lecture 8.
Lectures 9-11: Hypercontractivity, Friedgut's junta theorem, KKL inequality, Chang's lemma (notes by Anil Ada). 03/10/11: updated with lecture 11.
Lectures 12-13: Reverse Bonami-Beckner and expansion, Gaussian space (notes by Laura Eslava).
Lectures 14-15: Invariance Principle, Majority is stablest (notes by Athena Kardehi Moghaddam).

Assignments:

Tentative plan:

Introduction
Background: Hilbert spaces, Holder's inequality, L^p norms, Fourier analysis of finite Abelian groups.
Applications to theoretical computer science:

Testing: Linearity test; Dictatorship test.
Learning: Learning Fourier coefficients under the uniform distribution.
Circuit Complexity: Hastad's Switching lemma, Fourier spectrum of low-depth circuits [LMN]; Approximating low-depth circuits [Razborov-Smolensky].
Communication Complexity: Polynomial method.

Influences; Discrete isoperimetric inequality.
Noise operator; Discrete Log-Sobolov inequalities, Hyper-contractivity.
KKL inequality and Friedgut's Junta theorem.
Reverse Hypercontractivity and expansion.
Noise stability of Majority.
Berry-Esseen Theorem, Invariance principle, The proof of Majority is Stablest, Applications of Majority is Stablest.
Gaussian spaces; Chaos decomposition; General hypercontractivity, A square function inequality.
Russo-Margulis Lemma; Threshold Phenomena; Friedgut-Bourgain theorem and its generalization.
Noise sensitivity of linear threshold functions: Peres's Theorem.

Evaluation

Assignments: 60%
Presenting a paper at the end of the term: 20%
Scribing two lectures: 15%
Attending lectures: 5%

Potential Projects

J. Bourgain, Bounded orthogonal systems and the \Lambda(p)-set problem. Acta Math. 162 (1989), no. 3-4, 227-245.

E. Friedgut, On the measure of intersecting families, uniqueness and stability. Combinatorica 28 (2008), no. 5, 503528.

B. Green and T. Sanders, Boolean functions with small spectral norm. Geom. Funct. Anal. 18 (2008), no. 1, 144–162.

D. Ellis, E. Friedgut, and H. Pilpel, Intersecting Families of Permutations. Journal of the A.M.S. to appear.

J. Bourgain and G. Kalai, Influences of Variables and Threshold Intervals under Group Symmetries. Geom. Funct. Anal. 7 (1997), no. 3, 438-461

I. Benjamini, G. Kalai, and O. Schramm, Noise sensitivity of Boolean functions and applications to percolation, Inst. Hautes 'Etudes Sci. Publ. Math. (1999), 5–43 (2001)

O. Schramm and J. Steif, Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2) 171 (2010), no. 2, 619–672.

I. Benjamini, O. Schramm and D. Wilson, Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read. STOC'05

M. Braverman, Poly-logarithmic independence fools AC0 circuits, Journal of the ACM. to appear.

R. O'Donnell, M. Saks, O. Schramm and R. Servedio, Every decision tree has an influential variable. FOCS05

R. O'Donnell and R. Servedio, Learning monotone decision trees in polynomial time, SIAM Journal on Computing 37(3), pp. 827-844 (2007).