# CS 598AM: Analytic Methods in TCS and Quantum Information (Spring 2026) **Instructor:** Makrand Sinha **Time and Location:** Monday and Wednesday from 2-3:15pm in 1214 Siebel **Office Hours:** Monday and Wednesday 3:15-4pm in 3222 Siebel **Discussion Forum:** [EdStem](https://edstem.org/us/courses/94826/discussion/7545102) Please sign up with your illlinois.edu email with [this](https://edstem.org/us/join/wvqkkN) link. ### Description This is an advanced graduate-level theory course about tools from analysis that have interesting applications in algorithms, complexity theory, quantum information and machine learning theory. Tentative topics include: analysis on the Boolean hypercube, Gaussian and stochastic processes, concentration of measure and random matrix theory. Along the way we will come across many fundamental tools in probability, analysis and geometry and see nice applications of these techniques to combinatorics, algorithms, complexity, quantum pseudorandomness and quantum error correction. ### Grading Grading will be based on class participation. ### Prerequisites Background in algorithms and probability is recommended, however, the most important prerequisite for this course is mathematical maturity. No quantum background will be assumed for this course, as we will cover what is needed in the course. ### Resources - Lecture Notes posted on EdStem - [Textbook: Analysis of Boolean Functions](https://www.cs.cmu.edu/~odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf) by Ryan O' Donnell. Amazing textbook with lots of examples and exercises! - Other related courses at [Berkeley](https://www.avishaytal.org/cs-294-92-analysis-of-boolean-functions-spring-2025) (Avishay Tal), [MIT](https://www.avishaytal.org/cs-294-92-analysis-of-boolean-functions-spring-2025) (Dor Minzer), [UW](https://sites.math.washington.edu/~rothvoss/581A-fall-2025/analysisOfBooleanFunctions.pdf) (Thomas Rothvoss). Please email me if you find other good resources. - Lecture notes and Survey by Ramon Van Handel: [Probability in High Dimensions](https://web.math.princeton.edu/~rvan/APC550.pdf), [Stochastic Calculus](https://web.math.princeton.edu/~rvan/acm217/ACM217.pdf), [Random Matrix theory](http://arxiv.org/abs/2507.00346). ### Schedule ##### Part I: Analysis on Boolean and Gaussian Spaces - Week 1: Fundamentals of Fourier analysis on the Boolean hypercube Other Resources: Chapters 1 and 2 in Ryan's textbook - Week 2: Random restrictions and low-degree polynomials Other Resources: Chapters 3 and 4 in Ryan's textbook - Week 3: Hypercontractivity and applications such as sharp threshold, Friedgut or KKL theorem Other Resources: Chapter 10 in Ryan's textbook ### Future Schedule and Topics (tentative) - Week 4: p-biased anlaysis and global hypercontravity - Week 5: Gaussian space and Isoperimetric inequality - Week 6: Universality and Majority is stablest ##### Part II: Analysis via Paths - Martingales - Poincare inequalities - Sampling from convex bodies - Localization - Brownian motion and Ito calculus - Stochastic Localization - KLS conjecture - Stochastic ellipsoids - Robust isoperimetric inequalities ##### Part III: Analysis in Non-commutative settings - Trace power method and semi-circle law - Matrix Chernoff bounds and applications to tomography - Free probability theory - Matrix concentration via free probability - Matrix concentration by interpolation - Applications to quantum error correction - Designs and pseduorandom unitaries