CSE 599: Analytic and geometric methods in TCS

Winter 2023

MW 11:30am-12:50pm in

Instructor: James R. Lee

Office hours: TBD

Reference material:

Related content:

Course description:

This is an advanced graduate-level theory course about tools from analysis and geometry that have interesting applications in algorithms, complexity theory, and ML theory. Evaluation will be based on a small number of homeworks and student presentations. One topic per week, choice of topics will be guided by class interest.

I taught a version of this course back in prehistory. The set of topics will be mostly disjoint.

Possible topics:

  • High-dimensional expanders
  • Stochastic localization
  • Metric embedding theory
  • Generic chaining theory
  • Quantum information
  • Discrete Fourier analysis
  • Algebraic topology
  • ML Theory, e.g,
    • The edge of stability phenomenon
    • Stable diffusion, Doob interpolation in feature space

Lectures

Wed, Jan 04

Mon, Jan 09

Wed, Jan 11

Wed, Jan 18

Mon, Jan 23

Wed, Jan 25

Mon, Jan 30

Wed, Feb 01

Mon, Feb 06

Wed, Feb 08

Mon, Feb 13

Wed, Feb 15

Wed, Feb 22

Mon, Feb 27

Wed, Mar 01

Mon, Mar 06

Wed, Mar 08

Homeworks

  • You may discuss problems with your classmates, but when you write down the solutions, you should do so by yourself. You can use the internet and books for reference material but you should cite every source that you consulted (the name of the book or web page suffices). You should also cite any classmates with whom you discussed solutions.
  • We really, really prefer that homework be typeset.
  • In general, late submissions are not accepted, but if you have an emergency, let us know.
  • We follow the standard UW CSE policy for academic integrity.
  • The office hours are for general questions about material from the lecture and homework problems.
  • Please refer to university policies regarding disability accomodations or religious accommodations