Thomas Vidick


Simons Institute
Calvin Hall, UC Berkeley, Berkeley CA 94720, USA
vidick at csail dot mit dot edu
CV (Feb. 2013)

I am currently a Research Fellow at the Simons Institute in Berkeley. In Fall 2013 I was a Visiting Fellow in the Mathematics of Quanutm Information programme at the Newton Institute in Cambridge, UK. From Dec. 2011-July 2013 I was a postdoc in MIT's CSAIL, under the supervision of Scott Aaronson. Before coming to MIT I obtained my Ph.D. in UC Berkeley's theory group. My advisor was Umesh Vazirani. Prior to Berkeley, I obtained a Maitrise in mathematics from Ecole Normale Supérieure in Paris, and a Masters in computer science from Université Paris 7, under the supervision of Julia Kempe.

In June 2014 I will be joining the Computing and Mathematical Sciences Department at Caltech as an assistant professor.

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.


  • A parallel repetition theorem for entangled projection games, with Irit Dinur and David Steurer.
    Technical report arXiv:1310.4113, presented at QIP'14, to appear in CCC'14.

  • A survey on The Quantum PCP Conjecture, with Dorit Aharonov and Itai Arad.
    A version of the survey appeared in the complexity column of SIGACT News. The final version is available as arXiv:1309.7495; see also a related blog post.

  • A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians, with Zeph Landau and Umesh Vazirani.
    Technical report arXiv:1307.5143, presented at QIP'14, to appear in ITCS'14.

  • Three-player entangled XOR games are NP-hard to approximate.
    Appeared in FOCS'13. Available at arXiv:1302.1242.

  • Robust Randomness Amplifiers: Upper and Lower Bounds, with Matthew Coudron and Henry Yuen.
    Appeared in RANDOM'13. Conference proceedings. Available at arXiv:1305.6626.

  • Efficient rounding for the noncommutative Grothendieck inequality , with Assaf Naor and Oded Regev.
    Appeared in STOC'13. Conference proceedings. Available at arXiv:1210.7656.

  • Fully device-independent quantum key distribution , with Umesh Vazirani.
    Accepted as a plenary talk at QIP'13. To appear in ITCS'14. Also available as arXiv:1210.1810.

  • Quantum XOR games , with Oded Regev.
    To appear in CCC'13. Also accepted as a talk at QIP'13. Available at 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. Conference proceedings. Also available at arXiv:1207.0550.
    Invited for a plenary talk at QIP'13.

    This related chapter from my thesis presents an analysis of the entangled-prover linearity test, and may serve as a gentle introduction.

  • Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms , with Oded Regev.
    To appear in Journal of Operator Theory. arXiv:1206.4025.

  • Trevisan's extractor in the presence of quantum side information , with Anindya De, Christopher Portmann and Renato Renner.
    SIAM J. Comput 41(4), 2012. Journal version, arXiv:0912.5514.

  • Optimal counterfeiting attacks and generalizations for Wiesner's quantum money , with Abel Molina and John Watrous.
    Proceedings of TQC'12, Lecture Notes in Computer Science Volume 7582 (2013). Conference proceedings, arXiv:1202.4010.

  • Certifiable quantum dice - Or, exponential randomness expansion , with Umesh V. Vazirani
    Appeared in STOC'12. Conference proceedings. Also arXiv:1111.6054.
    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.

  • Explicit lower and upper bounds on the entangled value of multiplayer XOR games , with Jop Briet
    Comm. Math. Phys. 321(1), 2013. Journal version, arXiv:1108.5647. Accepted as a contributed talk to QIP'12.

  • 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. link, pdf.

  • All Schatten spaces endowed with the Schur product are Q-algebras , with Jop Briet, Harry Buhrman, and Troy Lee.
    Journal of Functional Analysis, 262(1), 2012. link

  • Parallel Repetition of Entangled Games , with Julia Kempe
    Appeared in STOC'11 and as a featured talk at QIP'11. arXiv:1012.4726.

  • 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). arXiv:1011.6448.

  • More non-locality with less entanglement , with Stephanie Wehner
    Phys. Rev. A 83, 052310 (2011). arXiv:1011.5206.

  • Better Gap-Hamming Lower Bounds via Better Round Elimination , with Joshua Brody, Amit Chakrabarti, Oded Regev, and Ronald de Wolf
    Appeared in RANDOM'10. Conference proceedings

  • Near-optimal extractors against quantum storage , with Anindya De
    Appeared in STOC'10 and as a contributed talk to QIP'10. arXiv:0911.4680

  • Multiplayer XOR games and quantum communication complexity with clique-wise entanglement , with Jop Briet, Harry Buhrman and Troy Lee
    To appear in Quantum Information and Computation (QIC). Technical report arXiv:0911.4007.

  • Entangled games are hard to approximate , with Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Ben Toner
    Invited to special issue of SICOMP dedicated to selected FOCS'08 papers (2009). arXiv:0704.2903

  • Sieve Algorithms for the Shortest Vector Problem are Practical , with Phong Nguyen
    Journal of Mathematical Cryptology, July 2008, Vol. 2, No. 2. pdf

  • Using Entanglement in Quantum Multi-Prover Interactive Proofs , with Julia Kempe, Hirotada Kobayashi, and Keiji Matsumoto
    Computational Complexity (special issue dedicated to selected CCC'08 papers), Vol. 18(2), p. 273--307 (2009). arXiv:0711.3715

  • Hauteur asymptotique des points de Heegner , with Guillaume Ricotta
    Canad. J. Math. 60 (2008). pdf


    I defended my Ph.D. thesis, on The Complexity of Entangled Games, in November 2011. It was awarded the Bernard Friedman Memorial Prize in Applied Mathematics from U.C. Berkeley's Department of Mathematics.

    Some recent (and not so recent) talks and video links