## Harmonic Analysis of Boolean Functions, Weizmann Institute

Spring 2008

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

Homework

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}n→{-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.

Additional useful reading includes the survey on threshold phenomena and influence by Gil Kalai and Muli Safra, and Daniel Štefankovič's master's thesis.