Tom Gur

Most-cited papers

Non-interactive proofs of proximity
Tom Gur, Ron D. Rothblum
2015Computational Complexity73 citations Open access
Semantic Scholar
Distribution Testing Lower Bounds via Reductions from Communication Complexity
Eric Blais, C. Canonne, Tom Gur
2019Cybersecurity and Cyberforensics Conference62 citations Open access
Semantic Scholar
Sublinear quantum algorithms for estimating von Neumann entropy
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
2021Electron. Colloquium Comput. Complex.44 citations
Semantic Scholar
An adaptivity hierarchy theorem for property testing
C. Canonne, Tom Gur
2017Computational Complexity39 citations
Semantic Scholar
Relaxed Locally Correctable Codes
Tom Gur, Govind Ramnarayan, Ron D. Rothblum
2018Information Technology Convergence and Services37 citations Open access
Semantic Scholar
Linear-Size Constant-Query IOPs for Delegating Computation
E. Ben-Sasson, A. Chiesa, Lior Goldberg, Tom Gur +2 more
2019IACR Cryptology ePrint Archive33 citations
Semantic Scholar
Proofs of Proximity for Distribution Testing
A. Chiesa, Tom Gur
2018Information Technology Convergence and Services30 citations
Semantic Scholar
A Hierarchy Theorem for Interactive Proofs of Proximity
Tom Gur, Ron D. Rothblum
2017Information Technology Convergence and Services30 citations
Semantic Scholar
Arthur-Merlin streaming complexity
Tom Gur, R. Raz
2013Information and Computation30 citations Open access
Semantic Scholar
On the Power of Relaxed Local Decoding Algorithms
Tom Gur, Oded Lachish
2020ACM-SIAM Symposium on Discrete Algorithms29 citations Open access
Semantic Scholar
Strong Locally Testable Codes with Relaxed Local Decoders
Oded Goldreich, Tom Gur, Ilan Komargodski
2015Electron. Colloquium Comput. Complex.29 citations Open access
Semantic Scholar
Information-theoretic generalization bounds for learning from quantum data
Matthias C. Caro, Tom Gur, C. Rouzé, Daniel Stilck França +1 more
2023arXiv.org23 citations
Semantic Scholar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
A. Chiesa, Tom Gur, Igor Shinkar
2020ACM-SIAM Symposium on Discrete Algorithms23 citations Open access
Semantic Scholar
Worst-case to average-case reductions via additive combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2022Electron. Colloquium Comput. Complex.22 citations
Semantic Scholar
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
A. Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018IEEE Annual Symposium on Foundations of Computer Science21 citations Open access
Semantic Scholar
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
Oded Goldreich, Tom Gur, Ron D. Rothblum
2015Electron. Colloquium Comput. Complex.21 citations Open access
Semantic Scholar
Quantum Communication Advantage in TFNP
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
2024Electron. Colloquium Comput. Complex.17 citations Open access
Semantic Scholar
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
2020Electron. Colloquium Comput. Complex.17 citations Open access
Semantic Scholar
Quantum Channel Testing in Average-Case Distance
Hugo Aaronson, G. Rosenthal, Sathyawageeswar Subramanian, Animesh Datta +1 more
2024arXiv.org16 citations
Semantic Scholar
Proof-Carrying Data from Arithmetized Random Oracles
Megan Chen, A. Chiesa, Tom Gur, Jack O'Connor +1 more
2023International Conference on the Theory and Application of Cryptographic Techniques16 citations Open access
Semantic Scholar
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP
Oded Goldreich, Tom Gur
2021Electron. Colloquium Comput. Complex.16 citations Open access
Semantic Scholar
Provable Advantage in Quantum PAC Learning
Tom Gur, Wilfred Salmon, Sergii Strelchuk
2023Electron. Colloquium Comput. Complex.15 citations
Semantic Scholar
Universal Locally Testable Codes
Oded Goldreich, Tom Gur
2016Electron. Colloquium Comput. Complex.15 citations
Semantic Scholar
High-precision and low-depth quantum algorithm design for eigenstate problems
Jin-Zhao Sun, Pei Zeng, Tom Gur, M. S. Kim
2024Science Advances14 citations Open access
Semantic Scholar
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar +1 more
2022Electron. Colloquium Comput. Complex.13 citations Open access
Semantic Scholar
Quantum learning algorithms imply circuit lower bounds
Srinivasan Arunachalam, A. Grilo, Tom Gur, I. C. Oliveira +1 more
2020IEEE Annual Symposium on Foundations of Computer Science12 citations Open access
Semantic Scholar
An Exponential Separation Between MA and AM Proofs of Proximity
Tom Gur, Yang P. Liu, Ron D. Rothblum
2018Computational Complexity12 citations Open access
Semantic Scholar
Every set in P is strongly testable under a suitable encoding
Irit Dinur, Oded Goldreich, Tom Gur
2018Electron. Colloquium Comput. Complex.11 citations
Semantic Scholar
Hypercontractivity on high dimensional expanders
Tom Gur, Noam Lifshitz, Siqi Liu
2021Electron. Colloquium Comput. Complex.10 citations Open access
Semantic Scholar
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Jahanara, M. Khodabandeh, N. Rajgopal +2 more
2024Symposium on the Theory of Computing9 citations Open access
Semantic Scholar
3-Query RLDCs Are Strictly Stronger Than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zheng
2025Symposium on the Theory of Computing8 citations Open access
Semantic Scholar
Quantum Proofs of Proximity
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, J. Thaler
2021Electron. Colloquium Comput. Complex.8 citations Open access
Semantic Scholar
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
2020SIAM journal on computing (Print)7 citations Open access
Semantic Scholar
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)
Eric Blais, C. Canonne, Tom Gur
2016Electron. Colloquium Comput. Complex.6 citations
Semantic Scholar
Testing Booleanity and the Uncertainty Principle
Tom Gur, Omer Tamuz
2012Chicago journal of theoretical computer science6 citations
Semantic Scholar
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
2025Electron. Colloquium Comput. Complex.5 citations Open access
Semantic Scholar
Streaming Zero-Knowledge Proofs
Graham Cormode, Marcel de Sena Dall'Agnol, Tom Gur, Chris Hickey
2023Cybersecurity and Cyberforensics Conference5 citations
Semantic Scholar
A Lower Bound for Relaxed Locally Decodable Codes
Tom Gur, Oded Lachish
2019Electron. Colloquium Comput. Complex.5 citations
Semantic Scholar
An Entropy Lower Bound for Non-Malleable Extractors
Tom Gur, Igor Shinkar
2018IEEE Transactions on Information Theory4 citations Open access
Semantic Scholar
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
2021SIAM Symposium on Simplicity in Algorithms3 citations Open access
Semantic Scholar
An algorithmic Polynomial Freiman-Ruzsa theorem
Davi Castro-Silva, J. Briët, Srinivasan Arunachalam, Arkopal Dutt +1 more
2026arXiv.org2 citations
Semantic Scholar
Classical and Quantum Polynomial Freiman-Ruzsa Algorithms
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur
2026Information Technology Convergence and Services2 citations
Semantic Scholar
Symmetric quantum computation
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
2025Information Technology Convergence and Services2 citations
Semantic Scholar
Information-theoretic generalization bounds for learning from quantum data
Matthias C. Caro, Tom Gur, C. Rouzé, Daniel Stilck França +1 more
2024Annual Conference Computational Learning Theory2 citations
Semantic Scholar
Distribution-Free Proofs of Proximity
Hugo Aaronson, Tom Gur, N. Rajgopal, Ron D. Rothblum
2023Electron. Colloquium Comput. Complex.2 citations Open access
Semantic Scholar
Trotter error compensation with polylogarithmic precision and nested-commutator scaling without ancillas
Xin-Zhao Wang, Shuo Zhou, Zi-Ruo Wang, Pei Zeng +4 more
20261 citations
Semantic Scholar
The power of time reversal in Hamiltonian property testing
Richard R. Allen, Matthias C. Caro, Yan-Lin Chen, Tom Gur +1 more
20261 citations
Semantic Scholar
Pseudo-deterministic Quantum Algorithms
Hugo Aaronson, Tom Gur, Jiawei Li
2026International Colloquium on Automata, Languages and Programming1 citations
Semantic Scholar
Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability
Tom Gur, Long-Cheng Li
20261 citations
Semantic Scholar
Algorithmic Polynomial Freiman-Ruzsa Theorems
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur
2025Electron. Colloquium Comput. Complex.1 citations
Semantic Scholar