 Winter 2024 Open problems in communication complexity (A. Rao)

Fall
2023
Quantum Information and Computation
(Coladangelo)
This course is an introduction to quantum information and computation aimed at graduate students. The goal of the course is to understand and familiarize with the fundamentals from an abstract point of view, while exploring several key applications. This will be almost entirely a theory course, with a small programming component (running algorithms on quantum devices in the cloud). Topics covered include: Qubits, quantum gates, and measurements. Entanglement and nonlocality. Density matrix formalism. Quantum algorithms: Simon’s, Grover search, Shor’s factoring, and Hamiltonian Simulation. Quantum errorcorrection.

Fall
2023
Sparsification, sampling, and optimization
(J. R. Lee)
Consider a function \(f : \mathbb{R}^n \to \mathbb{R}_+\) that can be written as a sum of a large number of functions \(f = f_1 + f_2 + \cdots\) from some class. When can this sum be sparsified in the sense that f can be approximated by a (nonnegative) weighted combination of a small number of the \(\{f_i\}\)? For many classes of functions, the answer is that, surprisingly, only about \(O(n)\) summands suffice (up to logarithmic factors). When this is possible, one can address the algorithmic questions: How to efficiently construct the sparsifier, and how to use sparse representations to optimize \(f\) efficiently.
This simple question has a wealth of applications in CS (especially in big data analysis), as well as in many areas of mathematics (especially in functional analysis and convex geometry). The course will focus on the (often deep) mathematical structures underlying sparsification problems, covering things like: Leverage scores, Lewis weights, generalized linear regression, spectral sparsification of graphs, matrix concentration, generic chaining theory, subspace embeddings and dimension reduction, submodularity, and lowrank approximation in numerical linear algebra.
 Spring 2023 Randomized algorithms (S. Oveis Gharan)

Winter
2023
Analytic and geometric methods in TCS
(J. R. Lee)
This is an advanced graduatelevel theory course about tools from analysis and geometry that have interesting applications in algorithms, complexity theory, and ML theory. Evaluation will be based on scribe notes and (possibly) student presentations. One topic per week, choice of topics will be guided by class interest.
 Generic chaining and extrema of random processes
 The KLS conjecture and stochastic localization
 Topological methods
 Highdimensional expanders
 Noise stability on the hypercube via Brownian motion
 The edge of stability in training deep NNs

Winter
2023
Lattices
(Rothvoss)
A lattice is discrete subgroup of \(\mathbb{R}^n\). Lattices are fundamental objects in discrete math with a rich set of applications to theoretical computer science, optimization and cryptography. We will see the following in this course:
 Introduction to lattices (Minkowski’s Theorems, the LLL algorithm, Knapsack cryptosystems, dual lattices, Hermite normal form, KZreduced basis)
 Algorithms for the Closest Vector problem (Babai’s algorithm, the Voronoi cell algorithm by Micciancio and Voulgaris)
 The Transference Theorems of Banaszczyk (Fourier analysis, the discrete Gaussian, transference theorem for Euclidean norm, transference theorem for arbitrary norms)
 Khintchine’s Flatness Theorem
 Lenstra’s algorithm for Integer programming in fixed dimension
 Lattice problems in NP intersect coNP
 Latticebased cryptography and Learning with Errors

Fall
2022
Intro to Quantum Computing
(J. R. Lee)
An introduction to the field of quantum computing from the perspective of computer science theory.
Quantum computing leverages the revolutionary potential of computers that exploit the parallelism of the quantum mechanical laws of the universe. Topics covered include:
 The axioms of quantum mechanics
 Quantum cryptography (quantum money, quantum key distribution)
 Quantum algorithms (Grover search, Shor’s algorithm)
 Quantum information theory (mixed states, measurements, and quantum channels)
 Quantum state tomography (learning and distinguishing quantum states)
 Quantum complexity theory
 Quantum error correction
 Quantum “supremacy”

Spring
2022
Lattices and Latticebased Cryptography
(Lin)
Point Lattices over the reals are remarkably useful in cryptography. Among many others, the Learning With Errors (LWE) assumption has changed the landscape of cryptography in recent years. Nearly every known cryptographic objective, from signatures, noninteractive zeroknowledge, fully homomorphic encryption, to attribute based encryption, can be based on LWE. Lattices is also one of the most widely used bases for developing postquantum and quantum cryptography, and it is a unique source of computational hardness with worstcase to averagecase connections. In this course, we will delve into lattices and latticebased cryptography. Topics covered, depending on time and interests, may include:
 basic properties of lattices,
 basic algorithms for attacking lattice problems and LWE,
 worstcase to averagecase, decision to search, reduction,
 basic cryptographic constructions: pseudorandom functions, signatures, chosenciphertext secure encryption, etc,
 powerful cryptographic constructions: fully homomorphic encryption, attributebased encryption, constraint pseudorandom function etc,
 lattices and quantum computation.
 Winter 2022 Intro to Quantum Computing (J. R. Lee)
 Winter 2022 Foundations of Fairness in Machine Learning (Jamie Morgenstern)
 Winter 2022 Modern Spectral Graph Theory (Oveis Gharan)
 Spring 2021 The art and science of positive definite matrices (J. R. Lee)
 Winter 2021 Sketching Algorithms (Y. T. Lee)
 Winter 2021 Cryptographic Protocols for PrivacyPreserving Computation (Tessaro)
 Winter 2021 Asymptotic Convex Geometry (Rothvoss)
 Fall 2020 Proof Complexity (Beame)
 Winter 2020 The Polynomial Paradigm in Algorithms (Shayan Oveis Gharan)
 Winter 2020 Foundations of Fairness in Machine Learning (Jamie Morgenstern)
 Fall 2019 Robustness in Machine Learning (Jerry Li)
 Fall 2019 Modern Coding Theory (Anup Rao)
 Spring 2019 Cryptography (Lin)
 Spring 2019 Randomized algorithms (J. Lee)
 Winter 2019 Probabilistic combinatorics (T. Rothvoss)
 Winter 2019 Theory of convex optimization (Y. T. Lee)
 Winter 2019 Communication complexity and lower bounds (A. Rao)
 Fall 2018 Algorithms through a geometric lens (I. Razenshteyn)
 Spring 2018 Competitive analysis via convex optimization (S. Bubeck and J. Lee)
 Winter 2018 Interplay between convex optimization and geometry (Y. T. Lee)
 Winter 2018 Student reading group  Lattices
 Fall 2017 Counting and sampling (Oveis Gharan)
 Spring 2017 Algorithms and uncertainty (Devanur and Karlin)
 Fall 2016 Randomized algorithms & probabilistic analysis (J. Lee)
 Spring 2016 Integer Optimization and Lattices (Rothvoss)
 Winter 2016 Entropy optimality (J. Lee)
 Fall 2015 Communication complexity (Rao)
 Spring 2015 Recent developments in approximation algorithms (Oveis Gharan)