Tom Gur

According to our database, Tom Gur authored at least 44 papers between 2013 and 2025.

Collaborative distances:

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

2025

Symmetric quantum computation.

Davi Castro-Silva, Tom Gur, Sergii Strelchuk

CoRR, January, 2025

2024

A Zero-Knowledge PCP Theorem.

Tom Gur, Jack O'Connor, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2024

Perfect Zero-Knowledge PCPs for #P.

Tom Gur, Jack O'Connor, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2024

Quantum Communication Advantage in TFNP.

Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

Electron. Colloquium Comput. Complex., 2024

Quantum Channel Testing in Average-Case Distance.

Hugo Aaronson, Gregory Rosenthal, Sathyawageeswar Subramanian, Animesh Datta, Tom Gur

CoRR, 2024

On the Power of Interactive Proofs for Learning.

Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Information-theoretic generalization bounds for learning from quantum data.

Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Streaming Zero-Knowledge Proofs.

Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey

Proceedings of the 39th Computational Complexity Conference, 2024

2023

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification.

Marcel Dall'Agnol, Tom Gur, Oded Lachish

SIAM J. Comput., December, 2023

Proof-Carrying Data From Arithmetized Random Oracles.

Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2023

Provable Advantage in Quantum PAC Learning.

Tom Gur, Wilfred Salmon, Sergii Strelchuk

Electron. Colloquium Comput. Complex., 2023

Distribution-Free Proofs of Proximity.

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum

Electron. Colloquium Comput. Complex., 2023

Derandomization of Cell Sampling.

Alexander Golovnev, Tom Gur, Igor Shinkar

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

2022

Quantum Proofs of Proximity.

Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler

Quantum, September, 2022

Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.

Alessandro Chiesa, Tom Gur, Igor Shinkar

SIAM J. Comput., 2022

Quantum Worst-Case to Average-Case Reductions for All Linear Problems.

Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

Electron. Colloquium Comput. Complex., 2022

Worst-Case to Average-Case Reductions via Additive Combinatorics.

Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2022

Hypercontractivity on high dimensional expanders.

Tom Gur, Noam Lifshitz, Siqi Liu

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP.

Oded Goldreich, Tom Gur

Theor. Comput. Sci., 2021

On the Power of Relaxed Local Decoding Algorithms.

Tom Gur, Oded Lachish

SIAM J. Comput., 2021

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces.

Tom Gur, Noam Lifshitz, Siqi Liu

Electron. Colloquium Comput. Complex., 2021

Sublinear quantum algorithms for estimating von Neumann entropy.

Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian

Electron. Colloquium Comput. Complex., 2021

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces.

Tom Gur, Noam Lifshitz, Siqi Liu

CoRR, 2021

An Exponential Separation Between MA and AM Proofs of Proximity.

Tom Gur, Yang P. Liu, Ron D. Rothblum

Comput. Complex., 2021

2020

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy.

Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish

Electron. Colloquium Comput. Complex., 2020

Quantum learning algorithms imply circuit lower bounds.

Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram

Electron. Colloquium Comput. Complex., 2020

2019

Distribution Testing Lower Bounds via Reductions from Communication Complexity.

Eric Blais, Clément L. Canonne, Tom Gur

ACM Trans. Comput. Theory, 2019

Linear-Size Constant-Query IOPs for Delegating Computation.

Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2019

A Lower Bound for Relaxed Locally Decodable Codes.

Tom Gur, Oded Lachish

Electron. Colloquium Comput. Complex., 2019

2018

An Entropy Lower Bound for Non-Malleable Extractors.

Tom Gur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2018

Every set in P is strongly testable under a suitable encoding.

Irit Dinur, Oded Goldreich, Tom Gur

Electron. Colloquium Comput. Complex., 2018

Spatial Isolation Implies Zero Knowledge Even in a Quantum World.

Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2018

Universal Locally Testable Codes.

Oded Goldreich, Tom Gur

Chic. J. Theor. Comput. Sci., 2018

Non-interactive proofs of proximity.

Tom Gur, Ron D. Rothblum

Comput. Complex., 2018

An adaptivity hierarchy theorem for property testing.

Clément L. Canonne, Tom Gur

Comput. Complex., 2018

2017

Relaxed Locally Correctable Codes.

Tom Gur, Govind Ramnarayan, Ron Rothblum

Electron. Colloquium Comput. Complex., 2017

Proofs of Proximity for Distribution Testing.

Alessandro Chiesa, Tom Gur

Electron. Colloquium Comput. Complex., 2017

A Hierarchy Theorem for Interactive Proofs of Proximity.

Tom Gur, Ron D. Rothblum

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

2016

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.).

Eric Blais, Clément Louis Canonne, Tom Gur

Electron. Colloquium Comput. Complex., 2016

2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs.

Oded Goldreich, Tom Gur, Ron Rothblum

Electron. Colloquium Comput. Complex., 2015

Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).

Oded Goldreich, Tom Gur, Ron D. Rothblum

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

2014

Strong Locally Testable Codes with Relaxed Local Decoders.

Oded Goldreich, Tom Gur, Ilan Komargodski

Electron. Colloquium Comput. Complex., 2014

2013

Arthur-Merlin Streaming Complexity.

Tom Gur, Ran Raz

Electron. Colloquium Comput. Complex., 2013

Testing Booleanity and the Uncertainty Principle.

Tom Gur, Omer Tamuz

Chic. J. Theor. Comput. Sci., 2013