# CS 598AM: Analytic Methods in TCS and Quantum Information (Spring 2026) **Instructor:** Makrand Sinha **Time and Location:** Monday and Wednesday at 2-3:15pm in 1214 Siebel ### 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. ### Tentative Topics ##### Part I: Analysis on Boolean and Gaussian Spaces - Fourier expansion and basic properties - Random restrictions and applications such as the switching lemma - Hypercontractivity and applications such as sharp threshold, Friedgut or KKL theorem - p-biased anlaysis and global hypercontravity - Gaussian space and Isoperimetric inequality - Universality - 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