Associate professor of Computing and Mathematical Sciences
California Institute of Technology, MC 305-16
1200 E. California Blvd.
Pasadena, CA 91125
office: Annenberg 207
phone: (626) 395-8684
- Two-player entangled games are NP-hard
With Anand Natarajan.
Technical report arXiv:1710.03062.
- A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries
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
With Andrea Coladangelo, Alex Grilo, Stacey Jeffery.
Technical report arXiv:1708.07359.
- Parallel DIQKD from parallel repetition
Technical report arXiv:1703.08508.
- Rigorous renormalization group method for ground space and low-energy states of local Hamiltonians
With Brenden Roberts, Olexei I. Motrunich.
Technical report arXiv:1703.01994.
- Overlapping Qubits
With Rui Chao, Ben Reichardt, Chris Sutherland. Proceedings of ITCS'17.
Technical report arXiv:1701.01062.
- Focus on device independent quantum information
With Stefano Pironio, Valerio Scarani. Closing editorial for New Journal of Physics special issue on device independence.
- QCMA hardness of ground space connectivity for commuting Hamiltonians
With David Gosset, Jenish Mehta. Quantum 1, 16 (2017).
Technical report arXiv:1610.03582.
- Robust self-testing of many-qubit states
With Anand Natarajan. Proceedings of STOC'17.
Technical report arXiv:1610.03574.
- Quantum Proofs
With John Watrous. NOW Foundations and Trends in Theoretical Computer Science, Vol. 11, No. 1-2 (2015) 1-215 (journal link).
Technical report arXiv:1610.01664.
- Test for a large amount of entanglement, using few measurements
With Rui Chao, Ben Reichardt, Chris Sutherland.
Technical report arXiv:1610.00771.
- Entanglement of approximate quantum strategies in XOR games
With Dimiter Ostrev.
Technical report arXiv:1609.01652.
- Privacy Amplification Against Active Quantum Adversaries
With Gil Cohen.
Technical report arXiv:1608.06318.
- A simple proof of Renner's exponential de Finetti theorem
With Henry Yuen.
Technical report arXiv:1608.04814.
- Simple and tight device-independent security proofs
With Rotem Arnon-Friedman, Renato Renner. Appeared in Qcrypt'16.
Technical report arXiv:1607.01797.
- Parallel repetition via fortification analytic view and the quantum case
With Mohammad Bavarian, Henry Yuen. Proceedings of ITCS'17.
Technical report arXiv:1603.05349.
- 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.
- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
With Itai Arad, Zeph Landau, Umesh Vazirani. Communications in Mathematical Physics, 2017. Also appeared in the proceedings of ITCS'17.
Technical report arXiv:1602.08828.
- A simple proof of the detectability lemma and spectral gap amplification
With Anurag Anshu, Itai Arad. Phys. Rev. B 93, 205142
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. Proceedings of STOC'17. Also 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.
- Non-signalling parallel repetition using de Finetti reductions
With Rotem Arnon-Friedman, Renato Renner. IEEE Transactions on Information Theory, 2014.
Technical report arXiv:1411.1582.
- A multiprover interactive proof system for the local Hamiltonian problem
With Joseph Fitzsimons. Proceedings of ITCS'15.
Technical report arXiv:1409.026.
- Unbounded entanglement can be needed to achieve the optimal success probability
With Laura Mancinska. Proceedings of ICALP'14. Journal version to appear in QIC.
Technical report arXiv:1402.4145.
- A parallel repetition theorem for entangled projection games
With Irit Dinur, David Steurer. Presented at QIP'14. Proceedings of CCC'14.
Technical report arXiv:1310.4113.
- The Quantum PCP Conjecture
With Dorit Aharonov, Itai Arad. A version of the survey appeared in the complexity column of SIGACT News. See also a related blog post.
Technical report arXiv:1309.7495.
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
With Zeph Landau, Umesh Vazirani. Proceedings of ITCS'14. Journal version in Nature Physics 11, 566-569 (2015).
Technical report arXiv:1307.5143.
- Robust Randomness Amplifiers, Upper and Lower Bounds
With Matthew Coudron, Henry Yuen. Proceedings of RANDOM'13.
Technical report arXiv:1305.6626.
- Three-player entangled XOR games are NP-hard to approximate
Appeared in FOCS'13.
Technical report arXiv:1302.1242.
- Efficient rounding for the noncommutative Grothendieck inequality
With Assaf Naor, Oded Regev. Proceedings of STOC'13.
Technical report arXiv:1210.7656.
- Fully device independent quantum key distribution
With Umesh Vazirani. Plenary talk at QIP'13. Proceedings of ITCS'14. Journal version in Phys. Rev. Lett. 113, 140501 (2014). See the erratum.
Technical report arXiv:1210.181.
- Quantum XOR games
With Oded Regev. Presented at QIP'13. Proceedings of CCC'13.
Technical report arXiv:1207.4939.
- A multi-prover interactive proof for NEXP sound against entangled provers
With Tsuyoshi Ito. Appeared in FOCS'12, co-winner of the FOCS 2012 Best Paper Award. Invited for a plenary talk at QIP'13.
Technical report arXiv:1207.055.
- A concentration inequality for the overlap of a vector on a large set, with application to communication complexity
Chicago Journal of Theoretical Computer Science, 2012.
- Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
With Oded Regev. Journal of Operator Theory 71(2), pp.491-506, Spring 2014 (link).
Technical report arXiv:1206.4025.
- Optimal counterfeiting attacks and generalizations for Wiesner's quantum money
With Abel Molina, John Watrous. Proceedings of TQC'12, Lecture Notes in Computer Science Volume 7582 (2013).
Technical report arXiv:1202.401.
- Parallel Repetition of Entangled Games
With Julia Kempe. Appeared in STOC'11 and as a featured talk at QIP'11.
Technical report arXiv:1012.4728.
- All Schatten spaces endowed with the Schur product are Q-algebras
With Jop Briet, Harry Buhrman, Troy Lee. Journal of Functional Analysis, 262(1), 2012.
- Certifiable quantum dice - Or, exponential randomness expansion
With Umesh Vazirani. Appeared in STOC'12. Shorter version published in a special theme issue "The foundations of computation, physics and mentality the Turing legacy" of Phil. Trans. R. Soc. A (2012) 370, 3432-3448.
Technical report arXiv:1111.6054.
- Explicit lower and upper bounds on the entangled value of multiplayer XOR games
With Jop Briet. Comm. Math. Phys. 321(1), 2013. Presented as a contributed talk at QIP'12.
Technical report arXiv:1108.5647.
- Does ignorance of the whole imply ignorance of the parts? - Large violations of non-contextuality in quantum theory
With Stephanie Wehner. Phys. Rev. Lett. 107, 030402 (2011).
Technical report arXiv:1011.6448.
- More non-locality with less entanglement
With Stephanie Wehner. Phys. Rev. A 83, 052310 (2011).
Technical report arXiv:1011.5206.
- Better Gap-Hamming Lower Bounds via Better Round Elimination
With Joshua Brody, Amit Chakrabarti, Oded Regev, Ronald de Wolf. Proceedings of RANDOM'10.
Technical report arXiv:912.5276.
- Trevisan's extractor in the presence of quantum side information
With Anindya De, Christopher Portmann, Renato Renner. SIAM J. Comput 41(4), 2012.
Technical report arXiv:912.5514.