**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**

**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.

- 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

Last modified: Sat Sep 27 19:27:28 Jerusalem Daylight Time 2008