Department:
MATH
Course Number:
8833 FDA
Hours - Lecture:
3
Hours - Lab:
0
Hours - Recitation:
0
Hours - Total Credit:
3
Typical Scheduling:
Not Regularly Scheduled Description:
Special Topics course crosslisted with CS 8803 DFA, by Will Perkins, Lev Reyzin, Elena Grigorescu, Georgios Piliouras and Santosh S Vempala.
Prerequisites:
Course Text:
TBA
Topic Outline:
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.