__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
*