CSE 599S: Analytical and geometric methods in the theory of computation
[course description
| lectures
| related material]
course description
Instructor: James
Lee,
CSE 640, tel. 616 4368
Location: CSE 503
Time: Mondays and
Wednesdays, 12-1:20pm
(occasionally Wed
12-2:30pm for those who can stay later)
Office hours: By appointment
Course evaluation: Homework (star-based scoring system)
About this course:
The course will feature 2-4 lecture vignettes on particularly nice or
surprising applications of analysis and geometry in algorithms and
complexity theory, with a focus on recent developments. As an
overarching theme, we'll look at why, when, and how continuous
mathematics makes a fundamental appearance in CS and discrete math.
A sample of techniques: Fourier analysis, additive combinatorics,
topological fixed point theory, spectral methods, representation theory,
and high-dimensional probability.
A sample of applications: Hardness of approximation, graph
partitioning,
compressed sensing, learning, explicit constructions, communication
and circuit complexity, and cryptography.
schedule of classes
schedule breaks: There
will be no class the week of Oct. 27 (FOCS
conference).
During the week of Nov 3-7, we will have guest lecturers.
schedule:
[I will post suplementary reading material here before each lecture. Lecture notes
will be posted before or soon after.]
- Lecture 1. Cheating with foams
Suggested reading: Feige-Kindler-O'Donnell (emphasis on this paper),
Alon-Klartag,
Kindler-O'Donnell-Rao-Wigderson,
and Raz (see the introduction here for a
general overview).
- Lecture 2. Spectral partitioning and near-optimal foams
Suggested reading: Same as Lecture 1, with an emphasis on Alon-Klartag.
See also Dan Spielman's lecture notes on spectral graph theory and on graphs and networks.
Related papers you could present for credit (one of these):
Parallel repetition in projection games and a concentration bound.
- Lecture 3. Cheating at unique games with semidefinite programming
Suggested reading: Rounding parallel repetitions of unique games.
Homework questions for these lectures
- Lecture 4. Conformal mappings, circle packings, and spectral geometry
Suggested reading: Spielman-Teng, and to a lesser extent Kelner.
See also Dan Spielman's lecture notes on spectral graph theory and on graphs and networks.
- Lecture 5. Uniformizing graphs, multi-commodity flows, and eigenvalues
Suggested reading: Biswal-Lee-Rao
- Lecture 6. The Borsuk-Ulam Theorem and some combinatorial applications
Suggested reading: Matousek's book, Chapter 2 and Section 3.3
and some recent applications of the Lovasz-Kneser theorem in TCS:
Dinur-Regev-Smyth and Theorem 1.3 of Alon, et. al.
- Lecture 7. The evasiveness conjecture
- Lecture 8a. A primer on simplicial complexes and collapsbility
Suggested reading:
Lovasz's lecture notes on Evasiveness of Graph Properties.
The original paper of Kahn, Saks, and Sturtevant.
- Lecture 9. Harmonic analysis of boolean functions
- Lecture 10. The unique games conjecture and MAX-CUT
- Lecture 11. The majority is stablest theorem and Lindeberg's proof of the CLT
- Lecture 12. Friedgut's junta theorem
- Lecture P1. From Integrality Gaps to Dictatorship Tests
- Lecture 13. Integrality gaps for Sparsest Cut
- Lecture 14. Analysis of the triangle inequalities
- Lecture 15. Isoperimetry and nearest-neighbor search
Suggested reading: Near-optimal hashing algorithms for approximate NNS in high dimensions,
Lower bounds on locality sensitive hashing
- Lecture 16. Structure vs. randomness and Roth's thereom on 3-term APs
related material