Analysis of Boolean Functions 

in

 Computer Science

Fall Semester 2002/3: Monday 12:00-14:00, Math 209

The course is given by Guy Kindler, and will cover topics concerning analysis of Boolean functions, and their relations to computer science.

Program for Talks

1. Introduction: Influence of variables, norms, Fourier representation. Voting systems: dictatorship, juntas, monotonicity.
2. Preliminaries: Testing the Hadamard code and the Long-code, and Noise-Sensitivity. 
3. Linear and Almost-Linear Functions: Almost linear functions are dictatorships.
4. Testing Juntas.  
5. Average Sensitivity and Juntas: The Bonami-Beckner Inequality, a theorem of Friedgut, extensions to the biased case.
6. Monotonicity and Symmetry: A lemma of Margulis, A theorem of Kahn, Kalai and Linial, threshold phenomena for graph-properties, first passage percolation.
7. Learning Juntas. 
8. Testing Proofs using three bits
9. Vertex-Cover is hard to approximate
10. Noise-Resistant Boolean Functions are Juntas

Home Assignments

1, 2, 3, 4,5, 6