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):
Students will be expected to read and present a paper to the class.
Wednesdays, 1:00 - 4:00pm. Klaus 2108.Schedule
9:35 am, Cherry Emmerson building, room 322
Low-degree algorithm, Goldreich-Levin, RO, ch 3
Statistical Queries, lower bounds
PCP theorem, UGC, the Long Code, and some history
Arindam Khan and Anand Louis
Diego Moran, following Alon, Dinur, Friedgut, Sudakov Graph Products and Fourier Analysis
Ioannis Panageas, following Friedgut's On the measure of intersecting families..
Abhishek Banerjee and Pushkar Tripathi
following: RO lecture 27
Ning Tan following Gavinsky et al.