# 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://drive.google.com/drive/folders/1I24DmAg1OM2ODkCyxcPiUHfDm5_3FMQv?usp=sharing) (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 - Weeks 3-4: Sharp Thresholds and Hypercontractivity Other Resources: - Chapter 10 in Ryan's textbook - Chapter 8 in Van Handel's lecture notes on High-dimensional Probability - Papers on global hypercontractivity: [arXiv: 1906.05568](https://arxiv.org/abs/1906.05568) and [arXiv:2307.01356](https://arxiv.org/pdf/2307.01356) - Week 5: Gaussian space, Universality and Majority is Stablest Other Resources: Chapter 11 in Ryan's textbook ##### Part II: Pathwise Analysis - Week 6: Martingales and Stochastic Processes Other Resources: Chapter 2 in Van Handel's Lecture Notes on Stochastic Calculus - Week 7: Brownian Motion and Stochastic Calculus Other Resources: Chapter 3-5 in Van Handel's Lecture Notes on Stochastic Calculus - Week 8: Time-change and Courtade-Kumar conjecture Other resources: [arXiv:2208.06508](https://arxiv.org/abs/2208.06508) - Week 9: Spring break ### Future Schedule and Topics (tentative) - Week 10: Stochastic Localization Other resources: Chapter 6 in [these](https://arxiv.org/abs/2406.01324) lecture notes by Klartag and Lehec - Week 11: Quantitative Central Limit Theorems and Stochastic Ellipsoids Other resources: [arXiv:1806.09087](https://arxiv.org/abs/1806.09087) and [arXiv:2504.05042](https://arxiv.org/abs/2504.05042) ### Future Schedule and Topics (tentative) ##### Part III: Analysis in Non-commutative settings - Week 12: Eigenvalue distribution of random matrices and Matrix Chernoff bounds Other resources: [Lecture notes](https://www.kunisky.com/static/teaching/2025fall-rmt/rmt-notes-2025.pdf) by Dmitry Kunisky - Week 13: Matrix Chernoff (contd) and applications to quantum learning and codes - Week 14-15: Matrix Concentration via Intrinsic freeness - Week 16: Polynomial method