MAT 218C: Analytical Methods in Discrete Mathematics
(a.k.a Discrete Fourier Analysis)

Time and Place:

Monday/Wednesday 2.00-3.50 P.M.,  MS 5118.
 

Instructor:

Benny Sudakov, MS 7911, bsudakov@math.ucla.edu.
 

Course description:

In this course we discuss various applications of Discrete Fourier Analysis to Discrete Mathematics and Computer Science. After briefly introducing necessary machinery the goal is to show many diverse application covering fields like, combinatorics, computational complexity, coding theory, probability and number theory. The course will be self contained so no prior knowledge of Fourier Analysis is required.

Sample Reading List:

There is no book which covers topics in this course. For similar courses which were taught by other people see:

Analytical Methods in Combinatorics and Computer-Science by Dinur and Friedgut

Harmonic Analysis of Boolean Functions by Hatami

Analysis of Boolean Functions by O'Donnell

Analysis of Boolean Functions by Sanders

Harmonic Analysis of Boolean Functions by Kindler

Polynomials of Random Variables by Mossel


Assignments:

  • Assignment 1
    •  
  • Assignment 2
    •  

    Course Outline (to be updated during the term):

  • Basic Fourier notions and Fourier basis for various finite Abelian groups, Convolutions, properties of Fourier coefficients, Parseval identity

    •  
  • Linearity Test and Complete graph test. Their simple analysis using Fourier techniques. (Complete graph test analysis is from Hastad and Wigderson). Application of Rusza-Szemeredi graphs to better bounds on the error probability of Complete graph test

    •  
  • Rusza-Szemeredi graphs and subsets with no 3-term arithmetic progression. Various Construction of Rusza-Szemeredi graphs. Proof of Roth theorem on the size of the densest subset of integers with no 3-term AP.

    •  
  • Influences of variables of Boolean functions, Edge isoperimetric inequality of binary cube, Coalition, and the Tribes functions, Noise operator and Bonami-Beckner hypercontractive inequality, Proof by KKL that there is always influential variable

    •  
  • Influences of variables, Thresholds for properties in random structures, Russo's Lemma, Condition for sharp thresholds, Sharp thresholds for perfect matching and non-2-colorability of uniform hypergraphs

    •  
  • Bounding variance using influences and inequality of Talagrand. Percolation-type model on the grid and variance of the weight of shortest path. Sublinear bound on the variance of the shortest path using Talagrand (from Benjamini-Kalai-Schramm paper).

    •  
  • Metric embeddings and distortion. Theorem of Enflo on embedding of cube in l_2. Logarithmic distortion for embedding expanders, Distortion for edit distance.

    •  
  • Coding theory, basic bounds for codes, linear codes, dual codes and MacWilliams identity. Linear programming bound for linear codes using Fourier

    •