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.


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:

Assignments:


Tentative plan:


Evaluation


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, 144162.
  • 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), 543 (2001)
  • O. Schramm and J. Steif, Quantitative noise sensitivity and exceptional times for percolation. Ann. of Math. (2) 171 (2010), no. 2, 619672.
  • 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).