Instructors

-Description-

Discrete Fourier analysis provides a set of techniques that have found wide applicability in mathematics and computer science. The underlying insight is that the projection of functions onto the Fourier basis can often provide the right angle in analyzing properties of various mathematical objects, such as boolean functions, graphs, PRGs, and sets of integers.

Topics will include (but are not limited to):

- Learning theory
- Social choice theory
- Hypercontractivity
- Property testing and applications to PCP's and hardness of approximation
- Threshold phenomena in random graphs and random CSP's

Students will be expected to read and present a paper to the class.

Wednesdays, 1:00 - 4:00pm. Klaus 2108.

Schedule- Jan. 10 Organization, pick a course meeting time
9:35 am, Cherry Emmerson building, room 322

- Jan. 13Introduction & Basics
- Jan. 20Social Choice, Influence, Noise Stability
- Jan. 25 Linearity & Dictator Testing
Wednesday, 1:00 pm, Klaus 2108. ref: DvM Lec 4 , DvM Lec 5, RO Lec 4

- Feb. 1 Learning, part 1
Low-degree algorithm, Goldreich-Levin, RO, ch 3

- Feb. 8 Learning, part 2
Statistical Queries, lower bounds

- Feb. 15 Hypercontractivity and KKL, Friedgut, FKN theorems
- Feb. 22 Introduction to hardness of approximation
PCP theorem, UGC, the Long Code, and some history

- Feb. 29 Hardness of Approximation: MAX 3-SAT and MAX-CUT
Arindam Khan and Anand Louis

- Mar. 7 SDP's and harmonic analysis
Cristobal Guzman, following Frank Vallentin's notes. Cristobal's slides

- Mar. 14 Applications to Extremal Combinatorics
Diego Moran, following Alon, Dinur, Friedgut, Sudakov Graph Products and Fourier Analysis

- Mar. 28 More Extremal Combinatorics
Ioannis Panageas, following Friedgut's On the measure of intersecting families..

- Apr. 4 Sharp Thresholds
Abhishek Banerjee and Pushkar Tripathi

- Apr. 11 Percolation
Andreas Galanis

- Apr. 18 Additive Combinatorics
following: RO lecture 27

- Apr. 25 Quantum communication complexity
Ning Tan following Gavinsky et al.

References

Course Notes

Surveys

Fourier Analysis of Boolean Functions

- KKL: "The Indluence of Variables on Boolean Functions"
- Friedgut's Theorem
- Majority Is Stablest
- BKKKL: "The Influence of Variables in Product Space"
- Talagrand: "On Russo's 0-1 Law"
- Beckner: "Inequalities in Fourier Analysis
- Hatami: "A Structure Theorem for Boolean Functions with small total influences"

Harmonic Analysis on Groups

Social Choice Theory

Applications to Hardness of Approximation

Applications to Learning

Applications to Property Testing

Sharp Thresholds

Applications to Percolation

Applications to Combinatorics

Applications to Number Theory

SDP's and Harmonic Analysis

Open Problems