# Publications

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

With Anand Natarajan.

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.

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.

- Overlapping Qubits
(Abstract)

With Rui Chao, Ben Reichardt, Chris Sutherland. Proceedings of ITCS'17.

Technical report arXiv:1701.01062.

- Focus on device independent quantum information
(Abstract)

With Stefano Pironio, Valerio Scarani. Closing editorial for New Journal of Physics special issue on device independence.

Journal link.

- QCMA hardness of ground space connectivity for commuting Hamiltonians
(Abstract)

With David Gosset, Jenish Mehta. Quantum 1, 16 (2017).

Technical report arXiv:1610.03582.

- Robust self-testing of many-qubit states
(Abstract)

With Anand Natarajan. Proceedings of STOC'17.

Technical report arXiv:1610.03574.

- Quantum Proofs
(Abstract)

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
(Abstract)

With Rui Chao, Ben Reichardt, Chris Sutherland.

Technical report arXiv:1610.00771.

- Entanglement of approximate quantum strategies in XOR games
(Abstract)

With Dimiter Ostrev.

Technical report arXiv:1609.01652.

- Privacy Amplification Against Active Quantum Adversaries
(Abstract)

With Gil Cohen.

Technical report arXiv:1608.06318.

- A simple proof of Renner's exponential de Finetti theorem
(Abstract)

With Henry Yuen.

Technical report arXiv:1608.04814.

- Simple and tight device-independent security proofs
(Abstract)

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
(Abstract)

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
(Abstract)

With Steven Heilman. Submitted

Technical report arXiv:1603.05620.

- Rigorous RG algorithms and area laws for low energy eigenstates in 1D
(Abstract), Video

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
(Abstract)

With Anurag Anshu, Itai Arad. Phys. Rev. B 93, 205142

Technical report arXiv:1602.01210.

- Constant-Soundness Interactive Proofs for Local Hamiltonians
(Abstract)

With Anand Natarajan.

Technical report arXiv:1512.02090.

- Survey on nonlocal games and operator space theory
(Abstract)

With Carlos Palazuelos. Journal of Mathematical Physics 57, 015220 (2016).

Technical report arXiv:1512.00419.

- Anchoring games for parallel repetition
(Abstract)

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
(Abstract)

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
(Abstract)

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
(Abstract)

With Joseph Fitzsimons. Proceedings of ITCS'15.

Technical report arXiv:1409.026.

- Unbounded entanglement can be needed to achieve the optimal success probability
(Abstract)

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
(Abstract)

With Irit Dinur, David Steurer. Presented at QIP'14. Proceedings of CCC'14.

Technical report arXiv:1310.4113.

- The Quantum PCP Conjecture
(Abstract)

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
(Abstract), Video

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
(Abstract)

With Matthew Coudron, Henry Yuen. Proceedings of RANDOM'13.

Technical report arXiv:1305.6626.

- Three-player entangled XOR games are NP-hard to approximate
(Abstract)

Appeared in FOCS'13.

Technical report arXiv:1302.1242.

- Efficient rounding for the noncommutative Grothendieck inequality
(Abstract)

With Assaf Naor, Oded Regev. Proceedings of STOC'13.

Technical report arXiv:1210.7656.

- Fully device independent quantum key distribution
(Abstract), Video

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
(Abstract)

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
(Abstract), Video

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
(Abstract)

Chicago Journal of Theoretical Computer Science, 2012.

Journal link.

- Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms
(Abstract)

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
(Abstract)

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
(Abstract)

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
(Abstract)

With Jop Briet, Harry Buhrman, Troy Lee. Journal of Functional Analysis, 262(1), 2012.

Journal link.

- Certifiable quantum dice - Or, exponential randomness expansion
(Abstract)

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
(Abstract)

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
(Abstract)

With Stephanie Wehner. Phys. Rev. Lett. 107, 030402 (2011).

Technical report arXiv:1011.6448.

- More non-locality with less entanglement
(Abstract)

With Stephanie Wehner. Phys. Rev. A 83, 052310 (2011).

Technical report arXiv:1011.5206.

- Better Gap-Hamming Lower Bounds via Better Round Elimination
(Abstract)

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
(Abstract)

With Anindya De, Christopher Portmann, Renato Renner. SIAM J. Comput 41(4), 2012.

Technical report arXiv:912.5514.