# News

- During Spring break Dorit Aharonov, David Gosset and myself taught a "Trends in Theory" workshop on Quantum Computation at UCSD. The workshop was organized by Shachar Lovett. You can find slides and lecture notes for the school here.
- This summer I am co-organizing a summer program on Challenges in quantum computation at the Simons Institute in Berkeley. The program will feature a workshop the week of June 11-15, 2018.
- I am proud to have been selected as a 2017 CIFAR Azrieli Global Scholar.
- French speakers, check out a video for a recent public lecture (in French) I delivered at the Institut Henri Poincare in Paris, as part of the special semester on Analysis in Quantum Information Theory.
- I organize the CMS Theory seminar.
- I help organize TCS+, an online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe. See our website for more information.

# Research Interests

My research is centered around problems at the interface of theoretical computer science, quantum information and cryptography. I like to use complexity theory as a tool to study problems in quantum computing, and quantum mechanical phenomena as a way to gain a new perspective on classical concepts from theoretical computer science.

# Teaching

- Spring 2018: CS38, Introduction to algorithms.
- Winter 2018: CS/CMS 139, Advanced Algorithms.
- Winter 2017: CS/CMS 139, Advanced Algorithms.
- Fall 2016: CS/Ph 120, 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.

# Recent papers

- Certifiable Randomness from a Single Quantum Device
(Abstract)

With Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani. Submitted.

Technical report arXiv:1804.0064.

- A three-player coherent state embezzlement game
(Abstract)

With Zhengfeng Ji, Debbie Leung.

Technical report arXiv:1802.04926.

- Low-degree testing for quantum states
(Abstract)

With Anand Natarajan. Presented at QIP'18. Submitted

Technical report arXiv:1801.03821.

- Entanglement in non-local games and the hyperlinear profile of groups
(Abstract)

With William Slofstra. Presented at QIP'18. Submitted.

Technical report arXiv:1711.10676.

- Practical device-independent quantum cryptography via entropy accumulation
(Abstract)

With Rotem Arnon-Friedman, Frederic Dupuis, Omar Fawzi, Renato Renner. Nature Communications 9:459(2018). Journal version of "Simple and tight device-independent security proofs".

Technical report arXiv:1607.01797.

- Two-player entangled games are NP-hard
(Abstract)

With Anand Natarajan. Proceedings of CCC'18.

Technical report arXiv:1710.03062.

- A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
(Abstract)

With Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin.

Technical report arXiv:1710.00557.

- Verifier-on-a-Leash new schemes for verifiable delegated quantum computation with quasilinear resources
(Abstract)

With Andrea Coladangelo, Alex Grilo, Stacey Jeffery. Presented at QIP'18. Submitted.

Technical report arXiv:1708.07359.

- Parallel DIQKD from parallel repetition
(Abstract)

Technical report arXiv:1703.08508.

- Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
(Abstract)

With Brenden Roberts, Olexei I. Motrunich.

Technical report arXiv:1703.01994.

# General-audience talks

- A public lecture (in French) delivered at the Institut Henri Poincare in Paris, as part of the special semester on Analysis in Quantum Information Theory.
- An introductory talk presenting some of my research in quantum cryptography at the Caltech Computes conference in November 2016.

# Expository notes

- A set of lecture notes I wrote for the UCSD Spring School on Quantum Computation: the circuit model, delegation of quantum computations, quantum games and self-testing, and interactive proofs with entangled provers. See the course page for more slides and notes.
- A simplified analysis (written in the format of a blog post) of my paper with Anand Natarajan presenting a robust test for n EPR pairs.
- A short proof of security for a protocol for device-independent quantum key distribution in parallel introduced by Jain, Miller and Shi.
- A simple proof of Renner's exponential de Finetti.
- An expository note, aimed at a general TCS audience, giving an analysis of the Blum-Luby-Rubinfeld linearity test as a game with entangled provers.

# Recent talks

- Entanglement requirements for non-local games, plenary talk at QIP 2018, Delft, Netherlands, 18 Jan 2018 (video).
- Tests for n qubits, KITP conference on Frontiers of Quantum Information Physics, KITP, Santa Barbara, 10 Oct 2017 (video).
- Entanglement Tests from Group Representations, Theory seminar, CQT Singapore, 23 Aug 2017.
- Entanglement Tests from Group Representations, Workshop on Probabilistic and Algebraic Methods in Quantum Information Theory, Texas A&M University, 17 Jul 2017.
- Robust and/or efficient tests for high-dimensional entanglement, TYQI 2017, Paris, Paris, 19 Jun 2017.
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D, IQC, Waterloo, Waterloo, 27 Mar 2017.
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D, QIP'17, Seattle, 19 Jan 2017 (video).
- Overlapping Qubits, Theory Colloquium, UT Austin, 02 Dec 2016.
- Overlapping Qubits, Workshop on Subfactor Theory, Quantum Field Theory, and Quantum Information, Harvard University, Cambridge, 09 Oct 2016.
- Overlapping Qubits, QuPa seminar day, Institut Henri Poincare, Paris, 07 Jul 2016.
- Device independent quantum cryptography, MIT CIS seminar, MIT, 16 Mar 2016.
- Anchoring games for parallel repetition, UCSD theory seminar, UCSD, 08 Feb 2016.
- Interactive proofs for local Hamiltonians, Workshop on the Frontiers of Quantum Information and Computer Science, QUICS, University of Maryland, 01 Oct 2015 (video).
- A multiprover interactive proof system for the local Hamiltonian problem, Quantum Hamiltonian Complexity Reunion at the Simons Institute, Berkeley, 04 May 2015.
- Non-Signalling Parallel Repetition Via de Finetti Reductions, UCLA theory seminar, UCLA, 28 Apr 2015.

# Students

- Jenish Mehta
- Andrea Coladangelo
- Milan Cvitkovic

# Postdocs

- Piyush Srivastava (CMI postdoc 2014-2016), now at TIFR.
- Omar Fawzi (2016), now an assistant professor at ENS Lyon.
- Gil Cohen (CMI postdoc 2015-2016), now at Princeton.
- Stacey Jeffery (IQIM postdoc 2014-2016), now a senior researcher at CWI.

# Service

- Managing Editor for Theory of Computing.
- Editor for Quantum.
- Member of the Steering Committee of the ITCS (Innovations in Theoretical Computer Science) series of conferences.
- Program Committee member for QIP 2012, QCRYPT 2012, FSTTCS 2013, QIP 2014, STOC 2014, RANDOM 2014, QCRYPT 2014, ITCS 2015, TQC 2015, ITCS 2016, QIP 2016, CCC 2016, FOCS 2016, ICALP'17, QCRYPT'17
**(chair)**, STOC'18, TQC'18. - Refereed for journals SICOMP, JACM, TOC, Nature, Complexity, QIC, PRL, PRA, PRX and conferences STOC, FOCS, ITCS, CCC, APPROX/RANDOM, Crypto, QIP.

# Workshop organization

- I organized the 2016 SoCal theory day at Caltech, on November 11th 2016.
- In October 2015, together with Artur Ekert, Renato Renner, Miklos Santha and Umesh Vazirani I organized a small workshop on foundations of randomness at the Stellenbosch Institute for Advanced Study (STIAS) in South Africa. See the webpage or this blog post and follow-up posts (first talk, day 1, day 2, day 3) for information on the workshop.
- In February 2014 I co-organized (with Dorit Aharonov and John Watrous) a one-week workshop on Quantum Games and Protocols at the Simons Institute in Berkeley. This was the first out of three workshops in the special semester on Quantum Hamiltonian Complexity at the institute. See the Simons website for videos of all talks, this blog post for a summary of the workshop, this one describing a (personal) scientific outcome of the workshop.

# Funding

- AFOSR MURI award "Scalable Certification of Quantum Computing Devices and Networks", 2018-2021.
- CIFAR Azrieli Global Scholar, 2017-2019.
- NSF CAREER "Interactions with Untrusted Quantum Devices", 02/2016-01/2021.
- Air Force Young Investigator Award "Towards a Secure Quantum Network", 2016-2019.
- Okawa Foundation Research Grant 2015-2016.