Thomas Vidick

ORCID

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 63

Top Venues

University of California, Berkeley, USA (PHD)

Education History

University of California, Berkeley, USA

PHD

Publications

Irit Dinur, Ting-Chun Lin, Thomas Vidick
Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes. CoRR (2024)
Thomas Vidick
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk). ICALP (2023)
Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick
Good Quantum LDPC Codes with Linear Time Decoders. STOC (2023)
James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang
Succinct Classical Verification of Quantum Computation. IACR Cryptol. ePrint Arch. 2022 (2022)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Anchored Parallel Repetition for Nonlocal Games. SIAM J. Comput. 51 (2) (2022)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2022)
Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, Thomas Vidick
Simple Tests of Quantumness Also Certify Qubits. CRYPTO (5) (2022)
James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang
Succinct Classical Verification of Quantum Computation. CoRR (2022)
James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang
Succinct Classical Verification of Quantum Computation. CRYPTO (2) (2022)
Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
Efficient Certifiable Randomness from a Single Quantum Device. CoRR (2022)
Eric Culf, Thomas Vidick, Victor V. Albert
Group coset monogamy games and an application to device-independent continuous-variable QKD. CoRR (2022)
Eric Culf, Thomas Vidick
A monogamy-of-entanglement game for subspace coset states. Quantum 6 (2022)
Thomas Vidick, Tina Zhang
Classical Proofs of Quantum Knowledge. EUROCRYPT (2) (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP* = RE. Commun. ACM 64 (11) (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. CoRR (2021)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM 68 (5) (2021)
Tony Metger, Thomas Vidick
Self-Testing of a Single Quantum Device Under Computational Assumptions. ITCS (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2021)
Eric Culf, Thomas Vidick
A monogamy-of-entanglement game for subspace coset states. CoRR (2021)
Tony Metger, Thomas Vidick
Self-testing of a single quantum device under computational assumptions. Quantum 5 (2021)
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick
Simpler Proofs of Quantumness. TQC (2020)
Zhengfeng Ji, Debbie W. Leung, Thomas Vidick
A three-player coherent state embezzlement game. Quantum 4 (2020)
Thomas Vidick, Tina Zhang
Classical zero-knowledge arguments for quantum computations. Quantum 4 (2020)
Andrea Coladangelo, Thomas Vidick, Tina Zhang
Non-interactive Zero-Knowledge Arguments for QMA, with Preprocessing. CRYPTO (3) (2020)
Thomas Vidick
Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate. SIAM J. Comput. 49 (6) (2020)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP*=RE. CoRR (2020)
Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas
Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018). SIAM J. Comput. 49 (5) (2020)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of the classical low individual degree test. CoRR (2020)
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick
Simpler Proofs of Quantumness. CoRR (2020)
Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick
A Quantum-Proof Non-malleable Extractor - With Application to Privacy Amplification Against Active Quantum Adversaries. EUROCRYPT (2) (2019)
Andrea Coladangelo, Alex Bredariol Grilo, Stacey Jeffery, Thomas Vidick
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources. EUROCRYPT (3) (2019)
Rotem Arnon Friedman, Renato Renner, Thomas Vidick
Simple and Tight Device-Independent Security Proofs. SIAM J. Comput. 48 (1) (2019)
Thomas Vidick, Tina Zhang
Classical zero-knowledge arguments for quantum computations. IACR Cryptol. ePrint Arch. 2019 (2019)
Andrea Coladangelo, Thomas Vidick, Tina Zhang
Non-interactive zero-knowledge arguments for QMA, with preprocessing. CoRR (2019)
Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
Quantum proof systems for iterated exponential time, and beyond. STOC (2019)
Andrea Coladangelo, Alex Bredariol Grilo, Stacey Jeffery, Thomas Vidick
Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. IACR Cryptol. ePrint Arch. 2019 (2019)
Alexandru Gheorghiu, Thomas Vidick
Computationally-Secure and Composable Remote State Preparation. FOCS (2019)
Umesh V. Vazirani, Thomas Vidick
Fully device independent quantum key distribution. Commun. ACM 62 (4) (2019)
Alexandru Gheorghiu, Thomas Vidick
Computationally-secure and composable remote state preparation. CoRR (2019)
Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick
A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries. IACR Cryptol. ePrint Arch. 2019 (2019)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
Certifiable Randomness from a Single Quantum Device. CoRR (2018)
Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
Quantum proof systems for iterated exponential time, and beyond. CoRR (2018)
Dimiter Ostrev, Thomas Vidick
Entanglement of approximate quantum strategies in XOR games. Quantum Inf. Comput. 18 (7&8) (2018)
Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
Quantum proof systems for iterated exponential time, and beyond. Electron. Colloquium Comput. Complex. 25 (2018)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. FOCS (2018)
Anand Natarajan, Thomas Vidick
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. FOCS (2018)
Anand Natarajan, Thomas Vidick
Two-Player Entangled Games are NP-Hard. Computational Complexity Conference (2018)
Rui Chao, Ben W. Reichardt, Chris Sutherland, Thomas Vidick
Overlapping Qubits. ITCS (2017)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Hardness amplification for entangled games via anchoring. STOC (2017)
Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick
A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries. CoRR (2017)
Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. ITCS (2017)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Parallel Repetition via Fortification: Analytic View and the Quantum Case. ITCS (2017)
Anand Natarajan, Thomas Vidick
A quantum linearity test for robustly verifying entanglement. STOC (2017)
Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, Thomas Vidick
Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. CoRR (2017)
Thomas Vidick, John Watrous
Quantum Proofs. Found. Trends Theor. Comput. Sci. 11 (1-2) (2016)
Rotem Arnon Friedman, Renato Renner, Thomas Vidick
Simple and tight device-independent security proofs. CoRR (2016)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Parallel repetition via fortification: analytic view and the quantum case. CoRR (2016)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Parallel repetition via fortification: analytic view and the quantum case. Electron. Colloquium Comput. Complex. 23 (2016)
Thomas Vidick
Three-Player Entangled XOR Games are NP-Hard to Approximate. SIAM J. Comput. 45 (3) (2016)
David Gosset, Jenish C. Mehta, Thomas Vidick
QCMA hardness of ground space connectivity for commuting Hamiltonians. CoRR (2016)
Rotem Arnon Friedman, Renato Renner, Thomas Vidick
Non-Signaling Parallel Repetition Using de Finetti Reductions. IEEE Trans. Inf. Theory 62 (3) (2016)
Steven Heilman, Thomas Vidick
A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem. CoRR (2016)
Anand Natarajan, Thomas Vidick
Robust self-testing of many-qubit states. CoRR (2016)
Matthew Coudron, Thomas Vidick
Interactive Proofs with Approximately Commuting Provers. ICALP (1) (2015)
Laura Mancinska, Thomas Vidick
Unbounded entanglement in nonlocal games. Quantum Inf. Comput. 15 (15&16) (2015)
Oded Regev, Thomas Vidick
Quantum XOR Games. ACM Trans. Comput. Theory 7 (4) (2015)
Irit Dinur, David Steurer, Thomas Vidick
A parallel repetition theorem for entangled projection games. Comput. Complex. 24 (2) (2015)
Mohammad Bavarian, Thomas Vidick, Henry Yuen
Anchoring games for parallel repetition. CoRR (2015)
Matthew Coudron, Thomas Vidick
Interactive proofs with approximately commuting provers. CoRR (2015)
Joseph F. Fitzsimons, Thomas Vidick
A Multiprover Interactive Proof System for the Local Hamiltonian Problem. ITCS (2015)
Anand Natarajan, Thomas Vidick
Constant-Soundness Interactive Proofs for Local Hamiltonians. CoRR (2015)
Laura Mancinska, Thomas Vidick
Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. ICALP (1) (2014)
Umesh V. Vazirani, Thomas Vidick
Robust device independent quantum key distribution. ITCS (2014)
Irit Dinur, David Steurer, Thomas Vidick
A Parallel Repetition Theorem for Entangled Projection Games. Computational Complexity Conference (2014)
Zeph Landau, Umesh V. Vazirani, Thomas Vidick
An efficient algorithm for finding the ground state of 1D gapped local hamiltonians. ITCS (2014)
Rotem Arnon Friedman, Renato Renner, Thomas Vidick
Non-signalling parallel repetition using de Finetti reductions. CoRR (2014)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory Comput. 10 (2014)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative grothendieck inequality. STOC (2013)
Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13 (3-4) (2013)
Dorit Aharonov, Itai Arad, Thomas Vidick
Guest column: the quantum PCP conjecture. SIGACT News 44 (2) (2013)
Irit Dinur, David Steurer, Thomas Vidick
A parallel repetition theorem for entangled projection games. CoRR (2013)
Oded Regev, Thomas Vidick
Quantum XOR Games. Computational Complexity Conference (2013)
Dorit Aharonov, Itai Arad, Thomas Vidick
The Quantum PCP Conjecture. CoRR (2013)
Matthew Coudron, Thomas Vidick, Henry Yuen
Robust Randomness Amplifiers: Upper and Lower Bounds. APPROX-RANDOM (2013)
Tsuyoshi Ito, Thomas Vidick
A multi-prover interactive proof for NEXP sound against entangled provers CoRR (2012)
Anindya De, Christopher Portmann, Thomas Vidick, Renato Renner
Trevisan's Extractor in the Presence of Quantum Side Information. SIAM J. Comput. 41 (4) (2012)
Assaf Naor, Oded Regev, Thomas Vidick
Efficient rounding for the noncommutative Grothendieck inequality CoRR (2012)
Tsuyoshi Ito, Thomas Vidick
A multi-prover interactive proof for NEXP sound against entangled provers. Electron. Colloquium Comput. Complex. 19 (2012)
Thomas Vidick
A concentration inequality for the overlap of a vector on a large set, with application to the communication complexity of the Gap-Hamming-Distance problem. Chic. J. Theor. Comput. Sci. 2012 (2012)
Abel Molina, Thomas Vidick, John Watrous
Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money. TQC (2012)
Umesh V. Vazirani, Thomas Vidick
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. STOC (2012)
Tsuyoshi Ito, Thomas Vidick
A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. FOCS (2012)
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick
Entangled Games Are Hard to Approximate. SIAM J. Comput. 40 (3) (2011)
Julia Kempe, Thomas Vidick
Parallel repetition of entangled games. STOC (2011)
Thomas Vidick
A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem. Electron. Colloquium Comput. Complex. 18 (2011)
Anindya De, Thomas Vidick
Near-optimal extractors against quantum storage. STOC (2010)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM (2010)
Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf
Better Gap-Hamming Lower Bounds via Better Round Elimination CoRR (2009)
Anindya De, Thomas Vidick
Near-optimal extractors against quantum storage. Electron. Colloquium Comput. Complex. 16 (2009)
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick
Using Entanglement in Quantum Multi-Prover Interactive Proofs. Comput. Complex. 18 (2) (2009)

Thomas Vidick.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Thomas Vidick