Georgia Inst. of Technology
College of Computing

CS 8002
Seminar: Analysis of Boolean Functions
Subhash Khot

Spring 2006

General Information and Announcements

This is an advanced topics seminar, intended for graduate students in theoretical computer science, mathematics and ACO program. The seminar would mostly consist of student presentations.  

Administrative Information

Lectures: Thu 1:00-3:00 pm.  Physics Bldg, Room S107

Professor: Subhash Khot - 234 CoC, 404-385-6603 khot@cc.gatech.edu

Lecture Schedule and Topics

 Lecture No.

Date

Topics and References

Presenter

1.

01/12/06

a.       Organizational meeting.

b.      Introduction to basic concepts: Boolean functions, influence, average sensitivity, voting schemes, dictatorship, juntas, MAJORITY.

c.       Fourier expansion, Linear functions, Monotone functions.

d.      Average sensitivity  \geq 1 for balanced functions . 

 Subhash Khot

2.

01/19, 01/26,  02/02

a.       Testing Linearity, Testing dictatroship, and Hastad's  3-bit  PCP

 

b.      Learning Juntas [Mossel, O’Donnell, Servedio ‘03] (.ps).

c.       Learning Constant Depth Circuits [Linial Mansour Nisan ‘93].

Subhash Khot  

 

Nikhil Devanur   

 

Parikshit Gopalan

4.

a.       Statement of Bonami- Beckner “Hypercontractive” theorem.

b.      Balanced Boolean function has at least one coordinate with "large" Influence [Kahn, Kalai, Linial ‘88] (.ps)

c.       BKKKL.

d.      Russo-Margulis theorem.

e.       Every monotone graph property has a sharp threshold [Friedgut, Kalai ‘96](.ps).

Subhash Khot

5.

 

6.

a.       Testing Monotonicity [Goldreich, et al ‘98](.pdf), [Dodis et al ‘99](.pdf).

Deeparnab Chakrabarti

7.

Metric Embeddings

a.       Hypercube into l2.

b.       l1-lower bound method. Expander into l1.

c.       {0,1}n/Rotations (quotient) into l1.

d.      Edit distance into l1.

e.       Bourgain’s theorem.

 Subhash Khot

8.

 

9.

 2/2

a.       Boolean functions with low average sensitivity depend on few coordinates [Friedgut ‘98] (.ps).

b.      Unique Games Conjecture ---> Hardness of  approximating Vertex Cover    [Khot, Regev ‘03] (.ps).

Ashok Ponnuswami  

10.

2/9

 

11.

3/30

a.       Banaszczyk’s Theorem. [Daniele Stefakovic’s Master’s Thesis] (.ps)

b.      Lattice Problems in NP \intersect co-NP [Aharonov Regev ‘04] (.ps).

Nisheeth Vishnoi  

12.

 

 

13.

4/7

 Yan Zhong Ding

14.

2/16

a.       Boolean Functions whose Fourier Transform is Concentrated on the first two levels. [Friedgut Kalai Naor ‘02] (.ps)

b.      Fourier Theoretic Perspective for the Condorcet Paradox and Arrow’s Theorem [Kalai ‘02] (.pdf)

 Tejas Iyer

15.

 

 

 

 

body>