Thomas Vidick

According to our database, Thomas Vidick authored at least 71 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources.

Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, Thomas Vidick

Theory Comput., 2024

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes.

Irit Dinur, Ting-Chun Lin, Thomas Vidick

CoRR, 2024

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes.

Irit Dinur, Ting-Chun Lin, Thomas Vidick

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

2023

Good Quantum LDPC Codes with Linear Time Decoders.

Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk).

Thomas Vidick

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Simple Tests of Quantumness Also Certify Qubits.

Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, Thomas Vidick

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

2022

A monogamy-of-entanglement game for subspace coset states.

Eric Culf, Thomas Vidick

Quantum, September, 2022

Anchored Parallel Repetition for Nonlocal Games.

Mohammad Bavarian, Thomas Vidick, Henry Yuen

SIAM J. Comput., 2022

Succinct Classical Verification of Quantum Computation.

James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang

IACR Cryptol. ePrint Arch., 2022

Group coset monogamy games and an application to device-independent continuous-variable QKD.

Eric Culf, Thomas Vidick, Victor V. Albert

CoRR, 2022

Efficient Certifiable Randomness from a Single Quantum Device.

Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

CoRR, 2022

2021

Self-testing of a single quantum device under computational assumptions.

Tony Metger, Thomas Vidick

Quantum, 2021

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device.

Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

J. ACM, 2021

MIP* = RE.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Commun. ACM, 2021

Quantum soundness of testing tensor codes.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Classical Proofs of Quantum Knowledge.

Thomas Vidick, Tina Zhang

Proceedings of the Advances in Cryptology - EUROCRYPT 2021, 2021

2020

Special Section on the Fiftieth Annual ACM Symposium on Theory of Computing (STOC 2018).

Thomas Vidick, Danupon Nanongkai, Dimitris Achlioptas

SIAM J. Comput., 2020

Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate.

Thomas Vidick

SIAM J. Comput., 2020

Classical zero-knowledge arguments for quantum computations.

Thomas Vidick, Tina Zhang

Quantum, 2020

A three-player coherent state embezzlement game.

Zhengfeng Ji, Debbie W. Leung, Thomas Vidick

Quantum, 2020

Quantum soundness of the classical low individual degree test.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

CoRR, 2020

Simpler Proofs of Quantumness.

Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Non-interactive Zero-Knowledge Arguments for QMA, with Preprocessing.

Andrea Coladangelo, Thomas Vidick, Tina Zhang

Proceedings of the Advances in Cryptology - CRYPTO 2020, 2020

2019

Simple and Tight Device-Independent Security Proofs.

Rotem Arnon Friedman, Renato Renner, Thomas Vidick

SIAM J. Comput., 2019

A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries.

Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin, Thomas Vidick

IACR Cryptol. ePrint Arch., 2019

Fully device independent quantum key distribution.

Umesh V. Vazirani, Thomas Vidick

Commun. ACM, 2019

Computationally-Secure and Composable Remote State Preparation.

Alexandru Gheorghiu, Thomas Vidick

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Entanglement of approximate quantum strategies in XOR games.

Dimiter Ostrev, Thomas Vidick

Quantum Inf. Comput., 2018

Quantum proof systems for iterated exponential time, and beyond.

Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

Electron. Colloquium Comput. Complex., 2018

Certifiable Randomness from a Single Quantum Device.

Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

CoRR, 2018

Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA.

Anand Natarajan, Thomas Vidick

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Two-Player Entangled Games are NP-Hard.

Anand Natarajan, Thomas Vidick

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

A quantum linearity test for robustly verifying entanglement.

Anand Natarajan, Thomas Vidick

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Hardness amplification for entangled games via anchoring.

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Overlapping Qubits.

Rui Chao, Ben W. Reichardt, Chris Sutherland, Thomas Vidick

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D.

Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Non-Signaling Parallel Repetition Using de Finetti Reductions.

Rotem Arnon Friedman, Renato Renner, Thomas Vidick

IEEE Trans. Inf. Theory, 2016

Three-Player Entangled XOR Games are NP-Hard to Approximate.

Thomas Vidick

SIAM J. Comput., 2016

Quantum Proofs.

Thomas Vidick, John Watrous

Found. Trends Theor. Comput. Sci., 2016

Parallel repetition via fortification: analytic view and the quantum case.

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Electron. Colloquium Comput. Complex., 2016

Robust self-testing of many-qubit states.

Anand Natarajan, Thomas Vidick

CoRR, 2016

A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem.

Steven Heilman, Thomas Vidick

CoRR, 2016

QCMA hardness of ground space connectivity for commuting Hamiltonians.

David Gosset, Jenish C. Mehta, Thomas Vidick

CoRR, 2016

2015

Quantum XOR Games.

Oded Regev, Thomas Vidick

ACM Trans. Comput. Theory, 2015

Unbounded entanglement in nonlocal games.

Laura Mancinska, Thomas Vidick

Quantum Inf. Comput., 2015

Constant-Soundness Interactive Proofs for Local Hamiltonians.

Anand Natarajan, Thomas Vidick

CoRR, 2015

Anchoring games for parallel repetition.

Mohammad Bavarian, Thomas Vidick, Henry Yuen

CoRR, 2015

A parallel repetition theorem for entangled projection games.

Irit Dinur, David Steurer, Thomas Vidick

Comput. Complex., 2015

A Multiprover Interactive Proof System for the Local Hamiltonian Problem.

Joseph F. Fitzsimons, Thomas Vidick

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Interactive Proofs with Approximately Commuting Provers.

Matthew Coudron, Thomas Vidick

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Efficient Rounding for the Noncommutative Grothendieck Inequality.

Assaf Naor, Oded Regev, Thomas Vidick

Theory Comput., 2014

Non-signalling parallel repetition using de Finetti reductions.

Rotem Arnon Friedman, Renato Renner, Thomas Vidick

CoRR, 2014

Robust device independent quantum key distribution.

Umesh V. Vazirani, Thomas Vidick

Proceedings of the Innovations in Theoretical Computer Science, 2014

An efficient algorithm for finding the ground state of 1D gapped local hamiltonians.

Zeph Landau, Umesh V. Vazirani, Thomas Vidick

Proceedings of the Innovations in Theoretical Computer Science, 2014

Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability.

Laura Mancinska, Thomas Vidick

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Guest column: the quantum PCP conjecture.

Dorit Aharonov, Itai Arad, Thomas Vidick

SIGACT News, 2013

Multipartite entanglement in XOR games.

Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick

Quantum Inf. Comput., 2013

The Quantum PCP Conjecture.

Dorit Aharonov, Itai Arad, Thomas Vidick

CoRR, 2013

Robust Randomness Amplifiers: Upper and Lower Bounds.

Matthew Coudron, Thomas Vidick, Henry Yuen

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Trevisan's Extractor in the Presence of Quantum Side Information.

Anindya De, Christopher Portmann, Thomas Vidick, Renato Renner

SIAM J. Comput., 2012

A multi-prover interactive proof for NEXP sound against entangled provers.

Tsuyoshi Ito, Thomas Vidick

Electron. Colloquium Comput. Complex., 2012

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.

Thomas Vidick

Chic. J. Theor. Comput. Sci., 2012

Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money.

Abel Molina, Thomas Vidick, John Watrous

Proceedings of the Theory of Quantum Computation, 2012

Certifiable quantum dice: or, true random number generation secure against quantum adversaries.

Umesh V. Vazirani, Thomas Vidick

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

The Complexity of Entangled Games.

Thomas Vidick

PhD thesis, 2011

Entangled Games Are Hard to Approximate.

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick

SIAM J. Comput., 2011

Parallel repetition of entangled games.

Julia Kempe, Thomas Vidick

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf

Proceedings of the Approximation, 2010

2009

Near-optimal extractors against quantum storage.

Anindya De, Thomas Vidick

Electron. Colloquium Comput. Complex., 2009

Using Entanglement in Quantum Multi-Prover Interactive Proofs.

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick

Comput. Complex., 2009

2008

Sieve algorithms for the shortest vector problem are practical.

Phong Q. Nguyen, Thomas Vidick

J. Math. Cryptol., 2008