- Another survey! I am happy that our survey with John Watrouns on Quantum Proofs has just appeared in Foundations and Trends in Theoretical Computer Science.
- In Spring 2016 I am teaching CS 101, Introduction to modern cryptography.
- I am grateful to the Air Force Office of Scientific Research for funding my research in quantum cryptography through the Air Force's Young Investigator Research Program, and to the National Science Foundation for awarding me a CAREER award on Interactions with Untrusted Quantum Devices.
- 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.
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.
- Quantum-Proof Extractors: Optimal up to Constant Factors
With Kai-Min Chung, Gil Cohen, Xiaodi Wu.
Technical report arXiv:1605.04194.
- Quantum Proofs
With John Watrous. NOW surveys in Foundations and Trends in Computer Science Vol. 11 No. 1-2, pp 1-215 (2016).
- A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem
With Steven Heilman. Submitted
Technical report arXiv:1603.05620.
- Parallel repetition via fortification analytic view and the quantum case
With Mohammad Bavarian, Henry Yuen.
Technical report arXiv:1603.05349.
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
With Itai Arad, Zeph Landau, Umesh Vazirani.
Technical report arXiv:1602.08828.
- A simple proof of the detectability lemma and spectral gap amplification
With Anurag Anshu, Itai Arad. Submitted
Technical report arXiv:1602.01210.
- Constant-Soundness Interactive Proofs for Local Hamiltonians
With Anand Natarajan.
Technical report arXiv:1512.02090.
- Survey on nonlocal games and operator space theory
With Carlos Palazuelos. Journal of Mathematical Physics 57, 015220 (2016).
Technical report arXiv:1512.00419.
- Anchoring games for parallel repetition
With Mohammad Bavarian, Henry Yuen. To be presented at QIP'16.
Technical report arXiv:1509.07466.
- Interactive proofs with approximately commuting provers
With Matthew Coudron. To be presented at QIP'16. Proceedings of ICALP'15.
Technical report arXiv:1510.00102.
- 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.
- Non-Signalling Parallel Repetition Via de Finetti Reductions, Simons Institute workshop on Information Theory in Complexity Theory and Combinatorics, Berkeley, 22 Apr 2015.
- Noncommutative Grothendieck inequalities and quantum two-player games, BMC Mini-Symposia on Quantum Information, Cambridge, UK, 01 Apr 2015.
- Quantum XOR Games, Banff workshop on Hypercontractivity and Log Sobolev Inequalities in Quantum Information Theory, Banff, 24 Feb 2015.
- A multiprover interactive proof system for the local Hamiltonian problem, QIP 2015, Sydney, 16 Jan 2015.
- The quantum PCP conjecture, PCQC inauguration workshop, Paris, 28 Aug 2014.
- Tutorial on the quantum PCP conjecture, AQIS, Kyoto, 20 Aug 2014.
- Parallel repetition of entangled projection games, ELC Workshop at the University of Tokyo on Quantum Complexity Theory, Tokyo, 18 Aug 2014.
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians, PiQuDos seminar at Perimeter Institute, Waterloo, 14 May 2014 (video).
- A Polynomial-time Algorithm for Finding Ground States of Gapped Local Hamiltonians in 1D, Workshop on Tensor Networks and Simulations, Simons Institute, Berkeley, 23 Apr 2014 (video).
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians, SQUINT, Santa Fe, 20 Feb 2014.
- Simulating quantum mechanics: the complexity of the local Hamiltonian problem, 32nd Annual Western States Mathematical Physics Meeting, Pasadena, 18 Feb 2014.
- Editor for Theory of Computing.
- 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.
- Refereed for journals SICOMP, JACM, TOC, Nature, Complexity, QIC, PRL, PRA, PRX and conferences STOC, FOCS, ITCS, CCC, APPROX/RANDOM, Crypto, QIP.
- 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.