Vidick, Thomas

Combined from CaltechAUTHORS

• Lewis, Laura and Zhu, Daiwei, et el. (2024) Experimental implementation of an efficient test of quantumness; Physical Review A; Vol. 109; No. 1; 012610; 10.1103/physreva.109.012610
• Mahadev, Urmila and Vazirani, Umesh, et el. (2022) Efficient Certifiable Randomness from a Single Quantum Device; 10.48550/arXiv.2204.11353
• Dinur, Irit and Hsieh, Min-Hsiu, et el. (2022) Good Quantum LDPC Codes with Linear Time Decoders; 10.48550/arXiv.2206.07750
• Lewis, Laura and Zhu, Daiwei, et el. (2022) Experimental Implementation of an Efficient Test of Quantumness; 10.48550/arXiv.2209.14316
• Culf, Eric and Vidick, Thomas, et el. (2022) Group coset monogamy games and an application to device-independent continuous-variable QKD; 10.48550/arXiv.2212.03935
• Bartusek, James and Kalai, Yael Tauman, et el. (2022) Succinct Classical Verification of Quantum Computation; 10.48550/arXiv.2206.14929
• Culf, Eric and Vidick, Thomas (2022) A monogamy-of-entanglement game for subspace coset states; Quantum; Vol. 6; Art. No. 791; 10.22331/q-2022-09-01-791
• Bavarian, Mohammad and Vidick, Thomas, et el. (2022) Anchored Parallel Repetition for Nonlocal Games; SIAM Journal on Computing; Vol. 51; No. 2; 214-253; 10.1137/21m1405927
• Ji, Zhengfeng and Natarajan, Anand, et el. (2022) Quantum soundness of testing tensor codes; ISBN 978-1-6654-2056-3; 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS); 586-597; 10.1109/FOCS52979.2021.00064
• Zhu, Daiwei and Kahanamoku-Meyer, Gregory D., et el. (2022) Interactive Protocols for Classically-Verifiable Quantum Advantage; 10.48550/arXiv.2112.05156
• Vidick, Thomas (2022) Almost synchronous quantum correlations; Journal of Mathematical Physics; Vol. 63; No. 2; Art. No. 022201; 10.1063/5.0056512
• Ji, Zhengfeng and Natarajan, Anand, et el. (2021) MIP* = RE; Communications of the ACM; Vol. 64; No. 11; 131-138; 10.1145/3485628
• Culf, Eric and Vidick, Thomas (2021) A monogamy-of-entanglement game for subspace coset states; 10.48550/arXiv.2107.13324
• Ji, Zhengfeng and Natarajan, Anand, et el. (2021) Quantum soundness of the classical low individual degree test; 10.48550/arXiv.2009.12982
• Metger, Tony and Vidick, Thomas (2021) Self-testing of a single quantum device under computational assumptions; Quantum; Vol. 5; Art. No. 544; 10.22331/q-2021-09-16-544
• Brakerski, Zvika and Christiano, Paul, et el. (2021) A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device; Journal of the ACM; Vol. 68; No. 5; Art. No. 31; 10.1145/3441309
• Vidick, Thomas and Zhang, Tina (2021) Classical Proofs of Quantum Knowledge; ISBN 9783030778859; Advances in Cryptology – EUROCRYPT 2021; 630-660; 10.1007/978-3-030-77886-6_22
• Coudron, Matthew and Stark, Jalex, et el. (2021) Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits; Communications in Mathematical Physics; Vol. 382; No. 1; 49-86; 10.1007/s00220-021-03963-w
• Ji, Zhengfeng and Leung, Debbie, et el. (2020) A three-player coherent state embezzlement game; Quantum; Vol. 4; Art. No. 349; 10.22331/q-2020-10-26-349
• Vidick, Thomas and Zhang, Tina (2020) Classical proofs of quantum knowledge; 10.48550/arXiv.2005.01691
• Regev, Oded and Vidick, Thomas (2020) Bounds on Dimension Reduction in the Nuclear Norm; ISBN 978-3-030-46761-6; Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2017-2019 Volume II; 279-299; 10.1007/978-3-030-46762-3_13
• Brakerski, Zvika and Koppula, Venkata, et el. (2020) Simpler Proofs of Quantumness; 10.4230/LIPIcs.TQC.2020.8
• Vidick, Thomas and Zhang, Tina (2020) Classical zero-knowledge arguments for quantum computations; Quantum; Vol. 4; Art. No. 266; 10.22331/q-2020-05-14-266
• Coladangelo, Andrea and Vidick, Thomas, et el. (2020) Non-interactive zero-knowledge arguments for QMA, with preprocessing; 10.48550/arXiv.1911.07546
• Vidick, Thomas (2020) Verifying quantum computations at scale: A cryptographic leash on quantum devices; Bulletin of the American Mathematical Society; Vol. 57; No. 1; 39-76; 10.1090/bull/1678
• Gheorghiu, Alexandru and Vidick, Thomas (2019) Computationally-Secure and Composable Remote State Preparation; ISBN 9781728149523; 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS); 1024-1033; 10.1109/focs.2019.00066
• Vidick, Thomas (2019) From Operator Algebras to Complexity Theory and Back; Notices of the American Mathematical Society; Vol. 66; No. 10; 1618-1627; 10.1090/noti1980
• Fitzsimons, Joseph and Ji, Zhengfeng, et el. (2019) Quantum proof systems for iterated exponential time, and beyond; ISBN 978-1-4503-6705-9; Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC '19); 473-480; 10.1145/3313276.3316343
• Aggarwal, Divesh and Chung, Kai-Min, et el. (2019) A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries; ISBN 978-3-030-17655-6; Advances in Cryptology - EUROCRYPT 2019; 442-469; 10.1007/978-3-030-17656-3_16
• Coladangelo, Andrea and Grilo, Alex B., et el. (2019) Verifier-on-a-Leash: new schemes for verifiable delegated quantum computation, with quasilinear resources; ISBN 978-3-030-17658-7; Advances in Cryptology - EUROCRYPT 2019; 247-277; 10.1007/978-3-030-17659-4_9
• Vazirani, Umesh and Vidick, Thomas (2019) Fully device independent quantum key distribution; Communications of the ACM; Vol. 62; No. 4; 133-133; 10.1145/3310974
• Briët, Jop and Buhrman, Harry, et el. (2019) Multiplayer XOR games and quantum communication complexity with clique-wise entanglement; 10.48550/arXiv.0911.4007v1
• Molina, Abel and Vidick, Thomas, et el. (2019) Optimal counterfeiting attacks and generalizations for Wiesner's quantum money; 10.48550/arXiv.1202.4010
• Vidick, Thomas and Yuen, Henry (2019) A simple proof of Renner's exponential de Finetti theorem; 10.48550/arXiv.1608.04814
• Vidick, Thomas (2019) Parallel DIQKD from parallel repetition; 10.48550/arXiv.1703.08508
• Vazirani, Umesh and Vidick, Thomas (2019) Certifiable Quantum Dice - Or, testable exponential randomness expansion; 10.48550/arXiv.1111.6054
• Heilman, Steven and Vidick, Thomas (2019) A Moment Majorization principle for random matrix ensembles with applications to hardness of the noncommutative Grothendieck problem; 10.48550/arXiv.1603.05620
• Arnon-Friedman, Rotem and Renner, Renato, et el. (2019) Simple and tight device-independent security proofs; SIAM Journal on Computing; Vol. 48; No. 1; 181-225; 10.1137/18M1174726
• Natarajan, Anand and Vidick, Thomas (2018) Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA; ISBN 9781538642306; 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS); 731-742; 10.1109/focs.2018.00075
• Brakerski, Zvika and Christiano, Paul, et el. (2018) A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device; ISBN 9781538642306; 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS); 320-331; 10.1109/focs.2018.00038
• Slofstra, William and Vidick, Thomas (2018) Entanglement in Non-local Games and the Hyperlinear Profile of Groups; Annales Henri Poincaré; Vol. 19; No. 10; 2979-3005; 10.1007/s00023-018-0718-y
• Chao, Rui and Reichardt, Ben W., et el. (2018) Test for a large amount of entanglement, using few measurements; Quantum; Vol. 2; Art. No. 92; 10.22331/q-2018-09-03-92
• Natarajan, Anand and Vidick, Thomas (2018) Two-Player Entangled Games are NP-Hard; ISBN 978-3-95977-069-9; 33rd Computational Complexity Conference (CCC 2018); Art. No. 20; 10.4230/LIPIcs.CCC.2018.20
• Ostrev, Dimiter and Vidick, Thomas (2018) Entanglement of approximate quantum strategies in XOR games; Quantum Information and Computation; Vol. 18; No. 7-8; 617-631; 10.48550/arXiv.1609.01652
• Arnon-Friedman, Rotem and Dupuis, Frédéric, et el. (2018) Practical device-independent quantum cryptography via entropy accumulation; Nature Communications; Vol. 9; Art. No. 459; PMCID PMC5792631; 10.1038/s41467-017-02307-4
• Roberts, Brenden and Vidick, Thomas, et el. (2017) Implementation of rigorous renormalization group method for ground space and low-energy states of local Hamiltonians; Physical Review B; Vol. 96; No. 21; Art. No. 214203; 10.1103/PhysRevB.96.214203
• Arad, Itai and Landau, Zeph, et el. (2017) Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D; 10.4230/LIPIcs.ITCS.2017.46
• Bavarian, Mohammad and Vidick, Thomas, et el. (2017) Parallel repetition via fortification: analytic view and the quantum case; ISBN 9783959770293; 8th Innovations in Theoretical Computer Science Conference; Art. No. 22; 10.4230/LIPIcs.ITCS.2017.22
• Arad, Itai and Landau, Zeph, et el. (2017) Rigorous RG algorithms and area laws for low energy eigenstates in 1D; Communications in Mathematical Physics; Vol. 356; No. 1; 65-105; 10.1007/s00220-017-2973-z
• Gosset, David and Mehta, Jenish C., et el. (2017) QCMA hardness of ground space connectivity for commuting Hamiltonians; Quantum; Vol. 1; 16; 10.22331/q-2017-07-14-16
• Bavarian, Mohammad and Vidick, Thomas, et el. (2017) Hardness amplification for entangled games via anchoring; ISBN 978-1-4503-4528-6; Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017; 303-316; 10.1145/3055399.3055433
• Natarajan, Anand and Vidick, Thomas (2017) A quantum linearity test for robustly verifying entanglement; ISBN 978-1-4503-4528-6; Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017; 1003-1015; 10.1145/3055399.3055468
• Chao, Rui and Reichardt, Ben W., et el. (2017) Overlapping Qubits; ISBN 9783959770293; 8th Innovations in Theoretical Computer Science Conference (ITCS 2017); Art. No. 48; 10.4230/LIPIcs.ITCS.2017.48
• Pironio, S. and Scarani, V., et el. (2016) Focus on device independent quantum information; New Journal of Physics; Vol. 18; No. 10; Art. No. 100202; 10.1088/1367-2630/18/10/100202
• Vidick, Thomas (2016) Three-Player Entangled XOR Games are NP-Hard to Approximate; SIAM Journal on Computing; Vol. 45; No. 3; 1007-1063; 10.1137/140956622
• Anshu, Anurag and Arad, Itai, et el. (2016) A simple proof of the detectability lemma and spectral gap amplification; Physical Review B; Vol. 93; No. 20; Art. No. 205142; 10.1103/PhysRevB.93.205142
• Chung, Kai-Min and Cohen, Gil, et el. (2016) Quantum-Proof Extractors: Optimal up to Constant Factors; 10.48550/arXiv.1605.04194
• Vidick, Thomas and Watrous, John (2016) Quantum Proofs; ISBN 978-1-68083-126-9; Foundations and Trends in Theoretical Computer Science; 1-215; 10.1561/0400000068
• Kempe, Julia and Vidick, Thomas (2016) On the Power of Entangled Quantum Provers; 10.48550/arXiv.0612063
• Natarajan, Anand and Vidick, Thomas (2016) Constant-Soundness Interactive Proofs for Local Hamiltonians; 10.48550/arXiv.1512.02090
• Bavarian, Mohammad and Vidick, Thomas, et el. (2016) Anchoring games for parallel repetition; 10.48550/arXiv.1509.07466
• Arnon-Friedman, Rotem and Renner, Renato, et el. (2016) Non-Signaling Parallel Repetition Using de Finetti Reductions; IEEE Transactions on Information Theory; Vol. 62; No. 3; 1440-1457; 10.1109/TIT.2016.2516022
• Palazuelos, Carlos and Vidick, Thomas (2016) Survey on nonlocal games and operator space theory; Journal of Mathematical Physics; Vol. 57; No. 1; Art. No. 015220; 10.1063/1.4938052
• Mančinska, Laura and Vidick, Thomas (2015) Unbounded entanglement in nonlocal games; Quantum Information and Computation; Vol. 15; No. 15-16; 1317-1332; 10.48550/arXiv.1402.4145
• Regev, Oded and Vidick, Thomas (2015) Quantum XOR Games; ACM Transactions on Computation Theory; Vol. 7; No. 4; Art. No. 15; 10.1145/2799560
• Landau, Zeph and Vazirani, Umesh, et el. (2015) A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians; Nature Physics; Vol. 11; No. 7; 566-569; 10.1038/nphys3345
• Coudron, Matthew and Vidick, Thomas (2015) Interactive Proofs with Approximately Commuting Provers; ISBN 978-3-662-47671-0; Automata, Languages, and Programming; 355-366; 10.1007/978-3-662-47672-7_29
• Dinur, Irit and Steurer, David, et el. (2015) A parallel repetition theorem for entangled projection games; Computational Complexity; Vol. 24; No. 2; 201-254; 10.1007/s00037-015-0098-3
• Fitzsimons, Joseph and Vidick, Thomas (2015) A Multiprover Interactive Proof System for the Local Hamiltonian Problem; ISBN 978-1-4503-3333-7; ITCS'15 Innovations in Theoretical Computer Science; 103-112; 10.1145/2688073.2688094
• Vazirani, Umesh and Vidick, Thomas (2014) Fully Device-Independent Quantum Key Distribution; Physical Review Letters; Vol. 113; No. 14; Art. No. 140501; 10.1103/PhysRevLett.113.140501
• Naor, Assaf and Regev, Oded, et el. (2014) Efficient Rounding for the Noncommutative Grothendieck Inequality; Theory of Computing; Vol. 10; No. 1; 257-295; 10.4086/toc.2014.v010a011
• Regev, Oded and Vidick, Thomas (2014) Elementary Proofs of Grothendieck Theorems for Completely Bounded Norms; Journal of Operator Theory; Vol. 71; No. 2; 491-506; 10.7900/jot.2012jul02.1947
• Dinur, Irit and Steurer, David, et el. (2014) A parallel repetition theorem for entangled projection games; ISBN 978-1-4799-3626-7; Proceedings of the Annual IEEE Conference on Computational Complexity; 197-208; 10.1109/CCC.2014.28
• Vazirani, Umesh and Vidick, Thomas (2014) Robust device independent quantum key distribution; ISBN 978-1-4503-2698-8; Proceedings of the 5th conference on Innovations in theoretical computer science; 35-36; 10.1145/2554797.2554802
• Landau, Zeph and Vazirani, Umesh, et el. (2014) An efficient algorithm for finding the ground state of 1D gapped local hamiltonians; ISBN 978-1-4503-2698-8; Proceedings of the 5th conference on Innovations in theoretical computer science; 301; 10.1145/2554797.2554825
• Mančinska, Laura and Vidick, Thomas (2014) Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability; ISBN 978-3-662-43947-0; Automata, Languages, and Programming; 835-846; 10.1007/978-3-662-43948-7_69
• Vidick, Thomas (2013) Three-player entangled XOR games are NP-hard to approximate; ISBN 978-0-7695-5135-7; IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS); 766-775; 10.1109/FOCS.2013.87
• Briët, Jop and Vidick, Thomas (2013) Explicit Lower and Upper Bounds on the Entangled Value of Multiplayer XOR Games; Communications in Mathematical Physics; Vol. 321; No. 1; 181-207; 10.1007/s00220-012-1642-5
• Aharonov, Dorit and Arad, Itai, et el. (2013) Guest Column: The Quantum PCP Conjecture; ACM SIGACT News; Vol. 44; No. 2; 47-79; 10.1145/2491533.2491549
• Naor, Assaf and Regev, Oded, et el. (2013) Efficient Rounding for the Noncommutative Grothendieck Inequality; ISBN 978-1-4503-2029-0; Proceedings of the forty-fifth annual ACM symposium on Theory of computing; 71-80; 10.1145/2488608.2488618
• Regev, Oded and Vidick, Thomas (2013) Quantum XOR Games; ISBN 978-0-7695-4997-2; 28th Annual IEEE Conference on Computational Complexity (CCC); 144-155; 10.1109/CCC.2013.23
• Molina, Abel and Vidick, Thomas, et el. (2013) Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money; ISBN 978-3-642-35655-1; Theory of Quantum Computation, Communication, and Cryptography; 45-64; 10.1007/978-3-642-35656-8_4
• Coudron, Matthew and Vidick, Thomas, et el. (2013) Robust Randomness Amplifiers: Upper and Lower Bounds; ISBN 978-3-642-40327-9; Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 468-483; 10.1007/978-3-642-40328-6_33
• Briët, Jop and Buhrman, Harry, et el. (2013) Multipartite entanglement in XOR games; Quantum Information and Computation; Vol. 13; No. 3-4; 334-360; 10.48550/arXiv.0911.4007
• Ito, Tsuyoshi and Vidick, Thomas (2012) A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers; ISBN 978-1-4673-4383-1; IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS); 243-252; 10.1109/FOCS.2012.11
• De, Anindya and Portmann, Christopher, et el. (2012) Trevisan's Extractor in the Presence of Quantum Side Information; SIAM Journal on Computing; Vol. 41; No. 4; 915-940; 10.1137/100813683
• Vazirani, Umesh and Vidick, Thomas (2012) Certifiable quantum dice; Philosophical Transactions A: Mathematical, Physical and Engineering Sciences; Vol. 370; No. 1971; 3432-3448; 10.1098/rsta.2011.0336
• Vidick, Thomas (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; Chicago Journal of Theoretical Computer Science; Vol. 18; No. 1; 1-12; 10.4086/cjtcs.2012.001
• Vazirani, Umesh and Vidick, Thomas (2012) Certifiable Quantum Dice Or, True Random Number Generation Secure Against Quantum Adversaries; ISBN 978-1-4503-1245-5; STOC'12 Symposium on Theory of Computing Conference; 61-76; 10.1145/2213977.2213984
• Briët, Jop and Buhrman, Harry, et el. (2012) All Schatten spaces endowed with the Schur product are Q-algebras; Journal of Functional Analysis; Vol. 262; No. 1; 1-9; 10.1016/j.jfa.2011.09.001
• Vidick, Thomas and Wehner, Stephanie (2011) Does Ignorance of the Whole Imply Ignorance of the Parts? Large Violations of Noncontextuality in Quantum Theory; Physical Review Letters; Vol. 107; No. 3; Art. No. 030402; 10.1103/PhysRevLett.107.030402
• Kempe, Julia and Kobayashi, Hirotada, et el. (2011) Entangled Games Are Hard to Approximate; SIAM Journal on Computing; Vol. 40; No. 3; 848-877; 10.1137/090751293
• Kempe, Julia and Vidick, Thomas (2011) Parallel Repetition of Entangled Games; ISBN 978-1-4503-0691-1; Proceedings of the 43rd annual ACM symposium on Theory of computing; 353-362; 10.1145/1993636.1993684
• Vidick, Thomas and Wehner, Stephanie (2011) More nonlocality with less entanglement; Physical Review A; Vol. 83; No. 5; Art. No. 052310; 10.1103/PhysRevA.83.052310
• De, Anindya and Vidick, Thomas (2010) Near-Optimal Extractors Against Quantum Storage; ISBN 978-1-4503-0050-6; Proceedings of the 42nd ACM symposium on Theory of computing; 161-170; 10.1145/1806689.1806713
• Kempe, J. and Vidick, T. (2010) Quantum Algorithms; ISBN 978-3-642-11913-2; Quantum Information, Computation and Cryptography: An Introductory Survey of Theory, Technology and Experiments; 309-342; 10.1007/978-3-642-11914-9_10
• Brody, Joshua and Chakrabarti, Amit, et el. (2010) Better Gap-Hamming Lower Bounds via Better Round Elimination; ISBN 978-3-642-15368-6; Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques; 476-489; 10.1007/978-3-642-15369-3_36
• Kempe, Julia and Kobayashi, Hirotada, et el. (2009) Using Entanglement in Quantum Multi-Prover Interactive Proofs; Computational Complexity; Vol. 18; No. 2; 273-307; 10.1007/s00037-009-0275-3
• Ricotta, Guillaume and Vidick, Thomas (2008) Hauteur asymptotique des points de Heegner; Canadian Journal of Mathematics; Vol. 60; No. 6; 1406-1436; 10.4153/CJM-2008-059-4
• Kempe, Julia and Kobayashi, Hirotada, et el. (2008) Entangled games are hard to approximate; ISBN 978-0-7695-3436-7; 49th Annual Symposium on Foundations-of-Computer-Science (FOCS); 447-456; 10.1109/FOCS.2008.8
• Nguyen, Phong Q. and Vidick, Thomas (2008) Sieve algorithms for the shortest vector problem are practical; Journal of Mathematical Cryptology; Vol. 2; No. 2; 181-207; 10.1515/jmc.2008.009
• Kempe, Julia and Kobayashi, Hirotada, et el. (2008) Using Entanglement in Quantum Multi-Prover Interactive Proofs; ISBN 978-0-7695-3169-4; 23rd Annual IEEE Conference on Computational Complexity; 211-222; 10.1109/CCC.2008.6