Tom Gur

According to our database, Tom Gur authored at least 44 papers between 2012 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

A Zero-Knowledge PCP Theorem.

Tom Gur, Jack O'Connor, Nicholas Spooner

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Quantum Communication Advantage in TFNP.

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

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

Quantum Channel Testing in Average-Case Distance.

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

CoRR, 2024

Perfect Zero-Knowledge PCPs for #P.

Tom Gur, Jack O'Connor, Nicholas Spooner

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 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

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

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

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Provable Advantage in Quantum PAC Learning.

Wilfred Salmon, Sergii Strelchuk, Tom Gur

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 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

Distribution-Free Proofs of Proximity.

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum

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

Derandomization of Cell Sampling.

Alexander Golovnev, Tom Gur, Igor Shinkar

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Proof-Carrying Data from Arithmetized Random Oracles.

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

Proceedings of the Advances in Cryptology - EUROCRYPT 2023, 2023

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

Worst-case to average-case reductions via additive combinatorics.

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

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

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

Quantum Proofs of Proximity.

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

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

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

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

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Quantum learning algorithms imply circuit lower bounds.

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

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

2020

On the Power of Relaxed Local Decoding Algorithms.

Tom Gur, Oded Lachish

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

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

Alessandro Chiesa, Tom Gur, Igor Shinkar

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

A Lower Bound for Relaxed Locally Decodable Codes.

Tom Gur, Oded Lachish

Electron. Colloquium Comput. Complex., 2019

Linear-Size Constant-Query IOPs for Delegating Computation.

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

Proceedings of the Theory of Cryptography - 17th International Conference, 2019

Every Set in P Is Strongly Testable Under a Suitable Encoding.

Irit Dinur, Oded Goldreich, Tom Gur

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

An Entropy Lower Bound for Non-Malleable Extractors.

Tom Gur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2018

Relaxed Locally Correctable Codes.

Tom Gur, Govind Ramnarayan, Ron D. Rothblum

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Proofs of Proximity for Distribution Testing.

Alessandro Chiesa, Tom Gur

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

An Exponential Separation Between MA and AM Proofs of Proximity.

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

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Spatial Isolation Implies Zero Knowledge Even in a Quantum World.

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

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

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

An Adaptivity Hierarchy Theorem for Property Testing.

Clément L. Canonne, Tom Gur

Proceedings of the 32nd Computational Complexity Conference, 2017

Distribution Testing Lower Bounds via Reductions from Communication Complexity.

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

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP.

Oded Goldreich, Tom Gur

Electron. Colloquium Comput. Complex., 2016

Universal Locally Testable Codes.

Oded Goldreich, Tom Gur

Electron. Colloquium Comput. Complex., 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

Non-Interactive Proofs of Proximity.

Tom Gur, Ron D. Rothblum

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 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

Strong Locally Testable Codes with Relaxed Local Decoders.

Oded Goldreich, Tom Gur, Ilan Komargodski

Proceedings of the 30th Conference on Computational Complexity, 2015

2013

Arthur-Merlin Streaming Complexity.

Tom Gur, Ran Raz

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Testing Booleanity and the Uncertainty Principle.

Tom Gur, Omer Tamuz

Electron. Colloquium Comput. Complex., 2012