Harmonic Analysis of Boolean Functions, Weizmann Institute

Meeting: Mondays, 16-18pm, Room 1
Lecturer: Guy Kindler (gkindler@gmail.com)
Exercise Grader: Amir Yehudayoff ()
Course Blog: (Course participants, please subscribe) http://boolean-functions.blogspot.com

Homework

• Homework 1
  
• Homework 2
  
• Homework 3
  
• Homework 4
  
• Homework 5
  

Lectures and lecture note assignments
You may use this sample file together with this definition file, as a template for your scribe notes. Also, you can try to use sources of previous scribe notes as a basis for yours. Please coordinate which scribes you write with Amir.

• Lecture 1: Course introduction, definitions of dictatoships, juntas, and influences. (by Gillat Kol PDF, source)
• Lecture 2: Influences of functions over products of probability spaces, variance, and the minimal influence of an unbiased Boolean function..(by Or Meir, PDF, source)
• Lecture 3: The discrete Fourier transform and its properties. (by Noam Arkind PDF, source)
• Lecture 4: Almost linear Boolean function are almost dictatorships [FKN]. (by Ofira Burstein PDF, source)
• Lecture 5: Almost linear Boolean function are almost dictatorships (cont.) (by Igor Shinkar PDF, source)
• Lecture 6: An analytic version of Arrow's theorem [Kalai]. (By Sergei Novikov PDF, )
• Lecture 7: An analytic version of Arrow's theorem [cont.]. (By Zvika Brakerski PDF, source)
• Lecture 8: Constraint testing. (By Shira Kritchman PDF, source)
• Lecture 9: Constraint testing (cont.)
• Lecture 10: Long-code testing and hardness of approximation. [Hastad] (By Ori Brostovski PDF, source)
• Lecture 11: Low-degree Boolean function are juntas. (By Eric Shellef PDF, source)
• Lecture 12: The Beckner inequality. (By Ori Gurel-Gurevich PDF, source)
• Lecture 13: The Beckner inequality. (By Ora Hefetz PDF, source)
• Lecture 14: Theshold phenomena of graph properties. (By Barak Zackay PDF, source)

Course Description
In this course we will explore the Fourier analysis of Boolean functions, ƒ:{-1,1}ⁿ→{-1,1}, and some of their numerous applications in computer science and beyond.

Prerequisites
The main prerequisite is some mathematical maturity. Students must also be comfortable with basic probability, calculus, and linear algebra.

Evaluation
Average exercise grade will cover 80% of the final mark, and the other 20% will be given for the scribes.

Related Material
There is no textbook for this course, however useful material and notes can be found on sites of similar courses.

• CMU course taught by Ryan O'Donnell.(most of the code for this webpage was stolen from Ryan's course site)
• Rutgers class by Guy Kindler
• Georgia Tech class by Subhash Khot
• Hebrew U. class by Irit Dinur and Ehud Friedgut
• University of Washington class by Nati Linial
• Berkeley class by Elchanan Mossel