Teaching

Courses

• Winter 2022: CMS139, Design & Analysis of Algorithms.
• Fall 2021: CS152, Introduction to cryptography
• Fall 2020: Cours FSMP, Interactive Proofs with Quantum Devices.
• Winter 2020: CMS139, Design & Analysis of Algorithms.
• Fall 2019: CS/Ph 120, Quantum cryptography.
• Winter 2019: CS/CMS 139, Design & Analysis of Algorithms.
• Fall 2018: CS152, Introduction to cryptography
• Spring 2018: CS38, Introduction to algorithms
• Winter 2018: CS/CMS 139, Advanced Algorithms
• Winter 2017: CS/CMS 139, Advanced Algorithms.
• Fall 2016: CS120, Quantum Cryptography. Also offered as an EdX course!
• Spring 2016: CS 101, Introduction to modern cryptography
• Winter 2016: CS/CMS 139, Advanced Algorithms
• Spring 2015: CS/CMS 139, Advanced Algorithms
• Fall 2014: CS286, Seminar in Computer Science. Topic: around the Quantum PCP conjecture

Lecture notes

Cours FSMP Interactive Proofs with Quantum Devices

These are lecture notes for a 10-week course given in Paris in Fall 2020. The notes are on the topic of “black-box testing” of quantum devics and provide a unified treatment of the single-device setting (Mahadev protocol for delegated computation) and the two-device setting (complexity of quantum multiprover interactive proofs, a.k.a. nonlocal games).

UCSD Spring School on Quantum Computation

• The circuit model
• Delegation of quantum computations
• Quantum games and self-testing
• Interactive proofs with entangled provers
• See the course page for more slides and notes.

CS/CMS 139, Advanced Algorithms

• Streaming algorithms and concentration inequalities
• The Experts/Multiplicative Weights Algorithm and Applications
• Semidefinite Programming
• Spectral Graph Theory
• Solving systems of linear equations
• Learning theory

CS/Ph 120, Quantum Cryptography

• Week 0: Basics of quantum information
• Week 4: Privacy amplification
• Week 10: Delegating quantum computations

CS286, Around the quantum PCP Conjecture

• Lecture 1: The PCP theorem, hardness of approximation, and multiplayer games
• Lecture 2: Equivalence of two statements of PCP, and a toy theorem
• Lecture 3: The linearity test and low-degree extensions
• Lecture 4: Dinur’s Proof of the PCP Theorem
• Lecture 5-6: Introduction to Hamiltonian Complexity, QMA-completeness of the Local Hamiltonian problem
• Lecture 7: Quantum PCP conjectures
• Lecture 8: A variant of QPCP for multiplayer entangled games
• Lecture 9: Tensor networks and the detectability lemma
• Lecture 10: Detectability Lemma, Decay of Correlations, and Area Law
• Lecture 11: 1-D Area Law
• Lecture 12: Classical and Quantum de Finetti theorems
• Lecture 13: Quantum de Finetti Theorems
• Lecture 14: Quantum de Finetti Theorems II
• Lecture 15: Tsirelson’s characterization of XOR games
• Lecture 16: 3-player entangled games and the role of monogamy
• Lecture 17: NP-hardness of computing the entangled value