Course announcement

Topics in Discrete Mathematics: Analysis of Boolean functions

MW 11:30 - 12:45 (Until mid October) Room 206 LOM (Mathematics Building)

Math 945a/CS 945a - A graduate course Mathematics/Computer Science

Instructor: Gil Kalai

Boolean functions are central objects in combinatorics, complexity theory, probability theory and other areas of mathematics and computer science. We will discuss Harmonic analysis of boolean functions and various applications to these areas.

Organizational meeting and Lectures I: SEPTEMBER 1, 11:30 room 206 LOM.

  • Lecture I: Collective coin flipping. (Randomness in distributed computing) The discrete cube, Boolean functions, influences of variables and Edge expansions. Basic examples and the example of tribes.
  • Lecture II: Discrete Isoperimetric resalts, general review, lower bounds for edge expansions: combinatorial proofs.
  • Lecture III: Fourier analysis on the discrete cube and the relation with influences and edge-expansion.
  • Lecture IV: Chinchine inequalities and Bonamie-Beckner inequalities. Edge-expansion inequalities revisited.
  • Lecture V: The proof of KKL theorem, some consequences, extensions and sharper forms. Consequences for random walks on the discrete cube.

  • Lecture VI, VII and VIII: Threshold behavior.
  • We review Russo's lemme and showed the application of KKL theorem to sharp threshold of graph properties. We discussed applications of the Margulis-Talagrand inequality, the case of a large group of symmetry and the case of small critical probabilities.
  • Special lecture: Ehud Friedgut: four proofs of an Erdos-Ko-Rado type theorem.
  • Lecture IX and X: Tail estomates and first passage percolation
  • Lectures XI and XII: Noise sensitivity and noise stability
  • Lecture XIII: An application: Arrow's theorem.

    Plan for the future: Special Classes:

    Monday October 25 + Wednesday October 27 Petros Bregiannis, Rooholla Ebrahimian and Stephan Winkler:

    Description of the result and Proof II from:

    5. E. Friedgut, G. Kalai and A. Naor, Boolean functions whose Fourier transform is concentrated on the first two levels, (with Ehud Friedgut and Assaf Naor) Adv. in Appl. Math., 29(2002), 427-437.

    AND description of the results of paper number 14.

    AND either proof 1 from paper 5) or some proofs from paper 14) or the basic proof from 16)

    Monday November 1 +(maybe) Wednesday Novenber 3 Pradipta Mitra + Sam Daitch + (maybe: Jian Zhang) Error correcting codes, background + Sections 1-3 from

    10. On the distance distribution of codes, G. Kalai and N. Linial, IEEE Trans. Inf. Th., 41(1995) 1467 - 1472.

    Monday November 8 +(maybe) Wednesday Novenber 10

    Yitong Yin and Ronny (Ramzi) Dakdouk

  • 15. Influences in Product Spaces, KKL and BKKKL Revisited To Appear, Combinatorics Probability and Computing.

    Monday November 15 +(maybe) Wednesday Novenber 17

    Kevin Chang, Aaron Johnson and Richard Yang

    learning.

    9. N. Linial Y. Mansour and N. Nisan, Constant-depth circuits, Fourier transform and learnability, Jour. Assoc. Comput. Mach., 40 (1993) 607 - 620.

    Links to papers (still partial) :

    1. J. Kahn, G. Kalai and N. Linial, The influence of variables on Boolean functions, Proc. 29-th Annual Symposium on Foundations of Computer Science, 68-80, Computer Society Press, 1988.

    2. E. Friedgut and G. Kalai, Every Monotone Graph Property has a Sharp Threshold Proc. AMS 124(1996), 2993-3002

    3. Talagrand, Michel(F-PARIS6-E) On Russo's approximate zero-one law. Ann. Probab. 22 (1994), no. 3, 1576--1587. you will find link in math sci net or jstor

    4. I. Benjamini, G. Kalai and O. Schramm, Improved variance bounds for first passage percolation, , Ann. Probab. 31 (2003), no. 4, 1970--1978.

    5. E. Friedgut, G. Kalai and A. Naor, Boolean functions whose Fourier transform is concentrated on the first two levels, (with Ehud Friedgut and Assaf Naor) Adv. in Appl. Math., 29(2002), 427-437.

    6. Itai Benjamini, G. Kalai and Oded Schramm, Noise Sensitivity of Boolean Functions And Applications to Percolation, Publ. I.H.E.S. 90 (1999), 5-43

    7. J. Bourgain and G. Kalai, Influences of variables and threshold intervals under group symmetries, GAFA 7 (1997), 438-461.

    8. E. Mossel and R. O'Donnell On the noise sensitivity of monotone functions, Random Structures & Algorithms 23(3), pp. 333-350 (2003). Conference version: Trends in Mathematics: Mathematics and Computer Science

    9. N. Linial Y. Mansour and N. Nisan, Constant-depth circuits, Fourier transform and learnability, Jour. Assoc. Comput. Mach., 40 (1993) 607 - 620.

    10. On the distance distribution of codes, G. Kalai and N. Linial, IEEE Trans. Inf. Th., 41(1995) 1467 - 1472.

  • 11. Boolean Functions with Low Average Sensitivity Depend on Few coordinates. Combinatorica Vol 18 (1) 1998 pp. 27-36..

  • 12. Sharp Thresholds of Graph Proprties, and the $k$-sat Problem. J. Amer. Math. Soc. 12 (1999), no. 4, 1017--1054. .

  • 13. Appendix to above paper, by Jean Bourgain.

  • 14. Noga Alon, Irit Dinur, Ehud Friedgut and Benny Sudakov, * Graph Products, Fourier Analysis and Spectral Techniques To appear in G.A.F.A. .

  • 15. Influences in Product Spaces, KKL and BKKKL Revisited To Appear, Combinatorics Probability and Computing.