![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Thomas Vidick
Person information
- award (2019): Presidential Early Career Award for Scientists and Engineers
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2011
- [b1]Thomas Vidick:
The Complexity of Entangled Games. University of California, Berkeley, USA, 2011
Journal Articles
- 2022
- [j26]Eric Culf, Thomas Vidick:
A monogamy-of-entanglement game for subspace coset states. Quantum 6: 791 (2022) - [j25]Mohammad Bavarian, Thomas Vidick, Henry Yuen
:
Anchored Parallel Repetition for Nonlocal Games. SIAM J. Comput. 51(2): 214-253 (2022) - 2021
- [j24]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
MIP* = RE. Commun. ACM 64(11): 131-138 (2021) - [j23]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): 31:1-31:47 (2021) - [j22]Tony Metger, Thomas Vidick:
Self-testing of a single quantum device under computational assumptions. Quantum 5: 544 (2021) - 2020
- [j21]Thomas Vidick, Tina Zhang:
Classical zero-knowledge arguments for quantum computations. Quantum 4: 266 (2020) - [j20]Zhengfeng Ji, Debbie W. Leung, Thomas Vidick:
A three-player coherent state embezzlement game. Quantum 4: 349 (2020) - [j19]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) - [j18]Thomas Vidick:
Erratum: Three-Player Entangled XOR Games are NP-hard to Approximate. SIAM J. Comput. 49(6): 1423-1427 (2020) - 2019
- [j17]Umesh V. Vazirani, Thomas Vidick:
Fully device independent quantum key distribution. Commun. ACM 62(4): 133 (2019) - [j16]Rotem Arnon Friedman
, Renato Renner, Thomas Vidick:
Simple and Tight Device-Independent Security Proofs. SIAM J. Comput. 48(1): 181-225 (2019) - 2018
- [j15]Dimiter Ostrev
, Thomas Vidick:
Entanglement of approximate quantum strategies in XOR games. Quantum Inf. Comput. 18(7&8): 617-631 (2018) - 2016
- [j14]Thomas Vidick
, John Watrous:
Quantum Proofs. Found. Trends Theor. Comput. Sci. 11(1-2): 1-215 (2016) - [j13]Thomas Vidick
:
Three-Player Entangled XOR Games are NP-Hard to Approximate. SIAM J. Comput. 45(3): 1007-1063 (2016) - [j12]Rotem Arnon Friedman
, Renato Renner, Thomas Vidick
:
Non-Signaling Parallel Repetition Using de Finetti Reductions. IEEE Trans. Inf. Theory 62(3): 1440-1457 (2016) - 2015
- [j11]Irit Dinur
, David Steurer, Thomas Vidick
:
A parallel repetition theorem for entangled projection games. Comput. Complex. 24(2): 201-254 (2015) - [j10]Laura Mancinska, Thomas Vidick:
Unbounded entanglement in nonlocal games. Quantum Inf. Comput. 15(15&16): 1317-1332 (2015) - [j9]Oded Regev, Thomas Vidick
:
Quantum XOR Games. ACM Trans. Comput. Theory 7(4): 15:1-15:43 (2015) - 2014
- [j8]Assaf Naor, Oded Regev, Thomas Vidick
:
Efficient Rounding for the Noncommutative Grothendieck Inequality. Theory Comput. 10: 257-295 (2014) - 2013
- [j7]Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick:
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13(3-4): 334-360 (2013) - [j6]Dorit Aharonov, Itai Arad, Thomas Vidick
:
Guest column: the quantum PCP conjecture. SIGACT News 44(2): 47-79 (2013) - 2012
- [j5]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) - [j4]Anindya De, Christopher Portmann, Thomas Vidick
, Renato Renner:
Trevisan's Extractor in the Presence of Quantum Side Information. SIAM J. Comput. 41(4): 915-940 (2012) - 2011
- [j3]Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick
:
Entangled Games Are Hard to Approximate. SIAM J. Comput. 40(3): 848-877 (2011) - 2009
- [j2]Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick
:
Using Entanglement in Quantum Multi-Prover Interactive Proofs. Comput. Complex. 18(2): 273-307 (2009) - 2008
- [j1]Phong Q. Nguyen, Thomas Vidick
:
Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol. 2(2): 181-207 (2008)
Conference and Workshop Papers
- 2023
- [c38]Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, Thomas Vidick:
Simple Tests of Quantumness Also Certify Qubits. CRYPTO (5) 2023: 162-191 - [c37]Thomas Vidick:
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk). ICALP 2023: 4:1-4:1 - [c36]Irit Dinur
, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick:
Good Quantum LDPC Codes with Linear Time Decoders. STOC 2023: 905-918 - 2022
- [c35]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: 195-211 - 2021
- [c34]Thomas Vidick, Tina Zhang:
Classical Proofs of Quantum Knowledge. EUROCRYPT (2) 2021: 630-660 - [c33]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
Quantum soundness of testing tensor codes. FOCS 2021: 586-597 - [c32]Tony Metger
, Thomas Vidick
:
Self-Testing of a Single Quantum Device Under Computational Assumptions. ITCS 2021: 19:1-19:12 - 2020
- [c31]Andrea Coladangelo, Thomas Vidick, Tina Zhang:
Non-interactive Zero-Knowledge Arguments for QMA, with Preprocessing. CRYPTO (3) 2020: 799-828 - [c30]Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick:
Simpler Proofs of Quantumness. TQC 2020: 8:1-8:14 - 2019
- [c29]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: 247-277 - [c28]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: 442-469 - [c27]Alexandru Gheorghiu, Thomas Vidick:
Computationally-Secure and Composable Remote State Preparation. FOCS 2019: 1024-1033 - [c26]Joseph F. Fitzsimons, Zhengfeng Ji
, Thomas Vidick, Henry Yuen:
Quantum proof systems for iterated exponential time, and beyond. STOC 2019: 473-480 - 2018
- [c25]Anand Natarajan, Thomas Vidick
:
Two-Player Entangled Games are NP-Hard. CCC 2018: 20:1-20:18 - [c24]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: 320-331 - [c23]Anand Natarajan, Thomas Vidick:
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. FOCS 2018: 731-742 - 2017
- [c22]Mohammad Bavarian, Thomas Vidick
, Henry Yuen:
Parallel Repetition via Fortification: Analytic View and the Quantum Case. ITCS 2017: 22:1-22:33 - [c21]Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick
:
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. ITCS 2017: 46:1-46:14 - [c20]Rui Chao
, Ben W. Reichardt, Chris Sutherland
, Thomas Vidick
:
Overlapping Qubits. ITCS 2017: 48:1-48:21 - [c19]Mohammad Bavarian, Thomas Vidick
, Henry Yuen:
Hardness amplification for entangled games via anchoring. STOC 2017: 303-316 - [c18]Anand Natarajan, Thomas Vidick
:
A quantum linearity test for robustly verifying entanglement. STOC 2017: 1003-1015 - 2015
- [c17]Matthew Coudron, Thomas Vidick
:
Interactive Proofs with Approximately Commuting Provers. ICALP (1) 2015: 355-366 - [c16]Joseph F. Fitzsimons, Thomas Vidick
:
A Multiprover Interactive Proof System for the Local Hamiltonian Problem. ITCS 2015: 103-112 - 2014
- [c15]Irit Dinur
, David Steurer
, Thomas Vidick
:
A Parallel Repetition Theorem for Entangled Projection Games. CCC 2014: 197-208 - [c14]Laura Mancinska, Thomas Vidick
:
Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. ICALP (1) 2014: 835-846 - [c13]Umesh V. Vazirani, Thomas Vidick
:
Robust device independent quantum key distribution. ITCS 2014: 35-36 - [c12]Zeph Landau, Umesh V. Vazirani, Thomas Vidick:
An efficient algorithm for finding the ground state of 1D gapped local hamiltonians. ITCS 2014: 301-302 - 2013
- [c11]Matthew Coudron, Thomas Vidick
, Henry Yuen:
Robust Randomness Amplifiers: Upper and Lower Bounds. APPROX-RANDOM 2013: 468-483 - [c10]Oded Regev, Thomas Vidick
:
Quantum XOR Games. CCC 2013: 144-155 - [c9]Assaf Naor, Oded Regev, Thomas Vidick
:
Efficient rounding for the noncommutative grothendieck inequality. STOC 2013: 71-80 - 2012
- [c8]Tsuyoshi Ito, Thomas Vidick
:
A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers. FOCS 2012: 243-252 - [c7]Umesh V. Vazirani, Thomas Vidick
:
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. STOC 2012: 61-76 - [c6]Abel Molina
, Thomas Vidick
, John Watrous:
Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money. TQC 2012: 45-64 - 2011
- [c5]Julia Kempe, Thomas Vidick
:
Parallel repetition of entangled games. STOC 2011: 353-362 - 2010
- [c4]Joshua Brody, Amit Chakrabarti
, Oded Regev, Thomas Vidick
, Ronald de Wolf:
Better Gap-Hamming Lower Bounds via Better Round Elimination. APPROX-RANDOM 2010: 476-489 - [c3]Anindya De, Thomas Vidick
:
Near-optimal extractors against quantum storage. STOC 2010: 161-170 - 2008
- [c2]Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick
:
Using Entanglement in Quantum Multi-prover Interactive Proofs. CCC 2008: 211-222 - [c1]Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick
:
Entangled Games are Hard to Approximate. FOCS 2008: 447-456
Editorship
- 2020
- [e1]Thomas Vidick:
11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA. LIPIcs 151, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-134-4 [contents]
Informal and Other Publications
- 2024
- [i39]Irit Dinur, Ting-Chun Lin, Thomas Vidick:
Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes. CoRR abs/2402.07476 (2024) - 2022
- [i38]Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
Efficient Certifiable Randomness from a Single Quantum Device. CoRR abs/2204.11353 (2022) - [i37]James Bartusek, Yael Tauman Kalai, Alex Lombardi, Fermi Ma, Giulio Malavolta
, Vinod Vaikuntanathan, Thomas Vidick, Lisa Yang:
Succinct Classical Verification of Quantum Computation. CoRR abs/2206.14929 (2022) - [i36]Eric Culf, Thomas Vidick, Victor V. Albert
:
Group coset monogamy games and an application to device-independent continuous-variable QKD. CoRR abs/2212.03935 (2022) - [i35]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: 857 (2022) - 2021
- [i34]Eric Culf, Thomas Vidick:
A monogamy-of-entanglement game for subspace coset states. CoRR abs/2107.13324 (2021) - [i33]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
Quantum soundness of testing tensor codes. CoRR abs/2111.08131 (2021) - 2020
- [i32]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
MIP*=RE. CoRR abs/2001.04383 (2020) - [i31]Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick:
Simpler Proofs of Quantumness. CoRR abs/2005.04826 (2020) - [i30]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
Quantum soundness of the classical low individual degree test. CoRR abs/2009.12982 (2020) - 2019
- [i29]Alexandru Gheorghiu, Thomas Vidick:
Computationally-secure and composable remote state preparation. CoRR abs/1904.06320 (2019) - [i28]Andrea Coladangelo, Thomas Vidick, Tina Zhang:
Non-interactive zero-knowledge arguments for QMA, with preprocessing. CoRR abs/1911.07546 (2019) - [i27]Thomas Vidick, Tina Zhang:
Classical zero-knowledge arguments for quantum computations. IACR Cryptol. ePrint Arch. 2019: 194 (2019) - [i26]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: 247 (2019) - [i25]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: 254 (2019) - 2018
- [i24]Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
Certifiable Randomness from a Single Quantum Device. CoRR abs/1804.00640 (2018) - [i23]Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen:
Quantum proof systems for iterated exponential time, and beyond. CoRR abs/1805.12166 (2018) - [i22]Joseph F. Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen:
Quantum proof systems for iterated exponential time, and beyond. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i21]Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, Thomas Vidick:
Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources. CoRR abs/1708.07359 (2017) - [i20]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 abs/1710.00557 (2017) - 2016
- [i19]Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel repetition via fortification: analytic view and the quantum case. CoRR abs/1603.05349 (2016) - [i18]Steven Heilman, Thomas Vidick:
A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem. CoRR abs/1603.05620 (2016) - [i17]Rotem Arnon Friedman
, Renato Renner, Thomas Vidick:
Simple and tight device-independent security proofs. CoRR abs/1607.01797 (2016) - [i16]Anand Natarajan, Thomas Vidick:
Robust self-testing of many-qubit states. CoRR abs/1610.03574 (2016) - [i15]David Gosset, Jenish C. Mehta, Thomas Vidick:
QCMA hardness of ground space connectivity for commuting Hamiltonians. CoRR abs/1610.03582 (2016) - [i14]Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel repetition via fortification: analytic view and the quantum case. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i13]Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Anchoring games for parallel repetition. CoRR abs/1509.07466 (2015) - [i12]Matthew Coudron, Thomas Vidick:
Interactive proofs with approximately commuting provers. CoRR abs/1510.00102 (2015) - [i11]Anand Natarajan, Thomas Vidick:
Constant-Soundness Interactive Proofs for Local Hamiltonians. CoRR abs/1512.02090 (2015) - 2014
- [i10]Rotem Arnon Friedman, Renato Renner, Thomas Vidick:
Non-signalling parallel repetition using de Finetti reductions. CoRR abs/1411.1582 (2014) - 2013
- [i9]Dorit Aharonov, Itai Arad, Thomas Vidick:
The Quantum PCP Conjecture. CoRR abs/1309.7495 (2013) - [i8]Irit Dinur, David Steurer, Thomas Vidick:
A parallel repetition theorem for entangled projection games. CoRR abs/1310.4113 (2013) - 2012
- [i7]Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. CoRR abs/1207.0550 (2012) - [i6]Assaf Naor, Oded Regev, Thomas Vidick:
Efficient rounding for the noncommutative Grothendieck inequality. CoRR abs/1210.7656 (2012) - [i5]Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i4]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. TR11 (2011) - 2009
- [i3]Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, Ronald de Wolf:
Better Gap-Hamming Lower Bounds via Better Round Elimination. CoRR abs/0912.5276 (2009) - [i2]Anindya De, Christopher Portmann, Thomas Vidick, Renato Renner:
Trevisan's extractor in the presence of quantum side information. CoRR abs/0912.5514 (2009) - [i1]Anindya De, Thomas Vidick:
Near-optimal extractors against quantum storage. Electron. Colloquium Comput. Complex. TR09 (2009)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-22 20:48 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint