Thomas Vidick

Contact

MIT 32-G628
Cambridge, MA 02139
vidick at csail dot mit dot edu

I am a Postdoc at 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. Before coming 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.

Publications

• Trevisan's extractor in the presence of quantum side information , with Anindya De, Christopher Portmann and Renato Renner.
  To appear in SICOMP, arXiv:0912.5514.
  
  
• Optimal counterfeiting attacks and generalizations for Wiesner's quantum money , with Abel Molina and John Watrous.
  Accepted as a talk at TQC'12, arXiv:1202.4010.
  
  
• Certifiable quantum dice - Or, exponential randomness expansion , with Umesh V. Vazirani
  To appear in STOC'12. Conference proceedings. Also arXiv:1111.6054.
  
  
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games , with Jop Briet
  arXiv:1108.5647, accepted as a contributed talk to QIP'12. To appear in Comm. Math. Phys.
  
  
• A concentration inequality for the overlap of a vector on a large set, with application to communication complexity
  pdf, submitted.
  
  
• 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
  Technical report arXiv:0911.4007, submitted.
  
  
• 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

Recent talks

• On the complexity of multi-prover interactive proofs with entangled provers: IQC Waterloo, Workshop on Recent Progress in Quantum Algorithms, 11th April 2012.
  
• On the complexity of multi-prover interactive proofs with entangled provers: MSR Cambridge, Theory reading group, 6th April 2012.
  
• Non-commutative Grothendieck inequality and Quantum XOR games: Northeastern university joint CS-Math seminar, 19th March 2012.
  
• Certifiable Quantum Dice: MIT TOC Colloquium, 21st February 2012.
  
• Quantum XOR games: Workshop on the geometry of entanglement, CIRM Marseille, 9-13 January 2012.
  
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games: Universidad Computense de Madrid, 28th September 2011.
  
• Exponential randomness amplification: Dagstuhl Seminar on "Quantum Cryptanalysis", 18-23 September 2011.
  
• Privacy ampliciation against quantum adversaries: Invited talk at QCRYPT 2011, Zurich, 14th September 2011.
  
• Parallel Repetition of Entangled Games: STOC 2011, San Jose, 7th June 2011.
  
• Parallel Repetition of Entangled Games: University of Washington theory seminar, 24th May 2011
  
• Direct product testing of entangled strategies: IQI Caltech, 3rd May 2011.
  
• Parallel Repetition of Entangled Games: LIAFA, Paris, 5th April 2011.
  
• Upper and lower bounds on the violation of tripartite Bell inequalities: PiQuDos seminar, Perimeter Institute, 30th March 2011.
  
• Parallel Repetition of Entangled Games: Berkeley theory lunch, 16th February 2011.
  
• Parallel Repetition of Entangled Games: Featured talk at QIP'11, Singapore, 10-14 January 2011.
  

Service

• Program Committee member of QIP 2012 and QCRYPT 2012
• Refereed for journals SICOMP, JACM, TOC, Complexity, QIC and conferences STOC, FOCS, CCC, APPROX/RANDOM, Crypto, QIP.

Other

• My bachelor's thesis, on the link between elliptic curves and transcendent numbers (we give a proof of the algebraic independence of Pi, Gamma(1/4) and exp(Pi) [Nesterenko, 1996]) : ps or pdf (in French)
  
• A few exercise sheets in computer science (the language is Caml) given since 2003/04 to a class of MP*. This is updated as I upload the subjects and their corrections.
  
• The report (in French) of my research internship at McGill university, Montréal, in February-August 2004, under the supervision of Henri Darmon, in algebraic number theory.
  
• My Master's thesis, made from March to July 2006 under the direction of Julia Kempe at LRI, Orsay (in French).
  
• While at Berkeley I organized the quantum reading group, and some of the notes we took may still be useful: Fall '09, Spring '10, Fall '10, and Spring '11.