Tom Gur

109 papers A* 15A 12Journal 77Unranked 5
YearRankTypeTitle / Venue / Authors
2026 A conf
Classical and Quantum Polynomial Freiman-Ruzsa Algorithms.
ITCS
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur
2026 J jnl
Pseudo-deterministic Quantum Algorithms.
CoRR
Hugo Aaronson, Tom Gur, Jiawei Li
2026 A conf
Symmetric Quantum Computation.
ITCS
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
2025 J jnl
$3$-Query RLDCs are Strictly Stronger than $3$-Query LDCs.
Electron. Colloquium Comput. Complex.
Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng
2025 J jnl
3-Query RLDCs are Strictly Stronger than 3-Query LDCs.
CoRR
Tom Gur, Dor Minzer, Guy Weissenberg, Kai Zhe Zheng
2025 A* conf
A Zero-Knowledge PCP Theorem.
STOC
Tom Gur, Jack O'Connor, Nicholas Spooner
2025 J jnl
Algorithmic Polynomial Freiman-Ruzsa Theorems.
Electron. Colloquium Comput. Complex.
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur
2025 J jnl
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies.
CoRR
Guy Goldberg, Tom Gur, Sidhant Saraogi
2025 J jnl
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies.
Electron. Colloquium Comput. Complex.
Guy Goldberg, Tom Gur, Sidhant Saraogi
2025 A* conf
Quantum Communication Advantage in TFNP.
STOC
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
2025 J jnl
Symmetric quantum computation.
CoRR
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
2024 J jnl
A Zero-Knowledge PCP Theorem.
CoRR
Tom Gur, Jack O'Connor, Nicholas Spooner
2024 J jnl
A Zero-Knowledge PCP Theorem.
IACR Cryptol. ePrint Arch.
Tom Gur, Jack O'Connor, Nicholas Spooner
2024 A conf
Distribution-Free Proofs of Proximity.
CCC
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
2024 A* conf
Information-theoretic generalization bounds for learning from quantum data.
COLT
Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
2024 A* conf
On the Power of Interactive Proofs for Learning.
STOC
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
2024 J jnl
On the Power of Interactive Proofs for Learning.
CoRR
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
2024 A* conf
Perfect Zero-Knowledge PCPs for #P.
STOC
Tom Gur, Jack O'Connor, Nicholas Spooner
2024 J jnl
Perfect Zero-Knowledge PCPs for #P.
CoRR
Tom Gur, Jack O'Connor, Nicholas Spooner
2024 J jnl
Perfect Zero-Knowledge PCPs for #P.
IACR Cryptol. ePrint Arch.
Tom Gur, Jack O'Connor, Nicholas Spooner
2024 A* conf
Provable Advantage in Quantum PAC Learning.
COLT
Wilfred Salmon, Sergii Strelchuk, Tom Gur
2024 J jnl
Quantum Channel Testing in Average-Case Distance.
CoRR
Hugo Aaronson, Gregory Rosenthal, Sathyawageeswar Subramanian, Animesh Datta, Tom Gur
2024 J jnl
Quantum Communication Advantage in TFNP.
CoRR
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
2024 J jnl
Quantum Communication Advantage in TFNP.
Electron. Colloquium Comput. Complex.
Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
2024 A* conf
Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
SODA
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2024 A conf
Streaming Zero-Knowledge Proofs.
CCC
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
2023 J jnl
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification.
SIAM J. Comput.
Marcel Dall'Agnol, Tom Gur, Oded Lachish
2023 — conf
Derandomization of Cell Sampling.
SOSA
Alexander Golovnev, Tom Gur, Igor Shinkar
2023 J jnl
Distribution-Free Proofs of Proximity.
CoRR
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
2023 J jnl
Distribution-Free Proofs of Proximity.
Electron. Colloquium Comput. Complex.
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum
2023 J jnl
Information-theoretic generalization bounds for learning from quantum data.
CoRR
Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
2023 J jnl
Proof-Carrying Data From Arithmetized Random Oracles.
IACR Cryptol. ePrint Arch.
Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner
2023 — conf
Proof-Carrying Data from Arithmetized Random Oracles.
EUROCRYPT (2)
Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner
2023 J jnl
Provable Advantage in Quantum PAC Learning.
Electron. Colloquium Comput. Complex.
Tom Gur, Wilfred Salmon, Sergii Strelchuk
2023 J jnl
Streaming Zero-Knowledge Proofs.
CoRR
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
2022 A* conf
Hypercontractivity on high dimensional expanders.
STOC
Tom Gur, Noam Lifshitz, Siqi Liu
2022 J jnl
Quantum Proofs of Proximity.
Quantum
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
2022 J jnl
Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
CoRR
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2022 J jnl
Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
Electron. Colloquium Comput. Complex.
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
2022 J jnl
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.
SIAM J. Comput.
Alessandro Chiesa, Tom Gur, Igor Shinkar
2022 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
J. ACM
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2022 J jnl
Worst-Case to Average-Case Reductions via Additive Combinatorics.
CoRR
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2022 J jnl
Worst-Case to Average-Case Reductions via Additive Combinatorics.
Electron. Colloquium Comput. Complex.
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2022 A* conf
Worst-case to average-case reductions via additive combinatorics.
STOC
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
2021 A* conf
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy.
SODA
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
2021 J jnl
An Exponential Separation Between MA and AM Proofs of Proximity.
Comput. Complex.
Tom Gur, Yang P. Liu, Ron D. Rothblum
2021 J jnl
Derandomization of Cell Sampling.
CoRR
Alexander Golovnev, Tom Gur, Igor Shinkar
2021 J jnl
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces.
Electron. Colloquium Comput. Complex.
Tom Gur, Noam Lifshitz, Siqi Liu
2021 J jnl
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces.
CoRR
Tom Gur, Noam Lifshitz, Siqi Liu
2021 J jnl
On the Power of Relaxed Local Decoding Algorithms.
SIAM J. Comput.
Tom Gur, Oded Lachish
2021 J jnl
Quantum Proofs of Proximity.
CoRR
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
2021 J jnl
Quantum Proofs of Proximity.
Electron. Colloquium Comput. Complex.
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
2021 A* conf
Quantum learning algorithms imply circuit lower bounds.
FOCS
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2021 J jnl
Sublinear quantum algorithms for estimating von Neumann entropy.
CoRR
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
2021 J jnl
Sublinear quantum algorithms for estimating von Neumann entropy.
Electron. Colloquium Comput. Complex.
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
2021 J jnl
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP.
Theor. Comput. Sci.
Oded Goldreich, Tom Gur
2020 J jnl
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy.
CoRR
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
2020 J jnl
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy.
Electron. Colloquium Comput. Complex.
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
2020 J jnl
An Entropy Lower Bound for Non-Malleable Extractors.
IEEE Trans. Inf. Theory
Tom Gur, Igor Shinkar
2020 A* conf
On the Power of Relaxed Local Decoding Algorithms.
SODA
Tom Gur, Oded Lachish
2020 J jnl
Quantum learning algorithms imply circuit lower bounds.
CoRR
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2020 J jnl
Quantum learning algorithms imply circuit lower bounds.
Electron. Colloquium Comput. Complex.
Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2020 A* conf
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.
SODA
Alessandro Chiesa, Tom Gur, Igor Shinkar
2020 J jnl
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Tom Gur, Igor Shinkar
2020 J jnl
Relaxed Locally Correctable Codes.
Theory Comput.
Tom Gur, Govind Ramnarayan, Ron Rothblum
2019 J jnl
A Lower Bound for Relaxed Locally Decodable Codes.
CoRR
Tom Gur, Oded Lachish
2019 J jnl
A Lower Bound for Relaxed Locally Decodable Codes.
Electron. Colloquium Comput. Complex.
Tom Gur, Oded Lachish
2019 J jnl
Distribution Testing Lower Bounds via Reductions from Communication Complexity.
ACM Trans. Comput. Theory
Eric Blais, Clément L. Canonne, Tom Gur
2019 A conf
Every Set in P Is Strongly Testable Under a Suitable Encoding.
ITCS
Irit Dinur, Oded Goldreich, Tom Gur
2019 — conf
Linear-Size Constant-Query IOPs for Delegating Computation.
TCC (2)
Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner
2019 J jnl
Linear-Size Constant-Query IOPs for Delegating Computation.
IACR Cryptol. ePrint Arch.
Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner
2019 J jnl
Strong Locally Testable Codes with Relaxed Local Decoders.
ACM Trans. Comput. Theory
Oded Goldreich, Tom Gur, Ilan Komargodski
2018 J jnl
An Entropy Lower Bound for Non-Malleable Extractors.
CoRR
Tom Gur, Igor Shinkar
2018 J jnl
An Entropy Lower Bound for Non-Malleable Extractors.
Electron. Colloquium Comput. Complex.
Tom Gur, Igor Shinkar
2018 A* conf
An Exponential Separation Between MA and AM Proofs of Proximity.
ICALP
Tom Gur, Yang P. Liu, Ron D. Rothblum
2018 J jnl
An Exponential Separation Between MA and AM Proofs of Proximity.
Electron. Colloquium Comput. Complex.
Tom Gur, Yang P. Liu, Ron D. Rothblum
2018 J jnl
An adaptivity hierarchy theorem for property testing.
Comput. Complex.
Clément L. Canonne, Tom Gur
2018 J jnl
Every set in P is strongly testable under a suitable encoding.
Electron. Colloquium Comput. Complex.
Irit Dinur, Oded Goldreich, Tom Gur
2018 J jnl
Non-interactive proofs of proximity.
Comput. Complex.
Tom Gur, Ron D. Rothblum
2018 A conf
Proofs of Proximity for Distribution Testing.
ITCS
Alessandro Chiesa, Tom Gur
2018 J jnl
Proofs of proximity for context-free languages and read-once branching programs.
Inf. Comput.
Oded Goldreich, Tom Gur, Ron D. Rothblum
2018 A conf
Relaxed Locally Correctable Codes.
ITCS
Tom Gur, Govind Ramnarayan, Ron D. Rothblum
2018 A* conf
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
FOCS
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
CoRR
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Spatial Isolation Implies Zero Knowledge Even in a Quantum World.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
2018 J jnl
Universal Locally Testable Codes.
Chic. J. Theor. Comput. Sci.
Oded Goldreich, Tom Gur
2017 A conf
A Hierarchy Theorem for Interactive Proofs of Proximity.
ITCS
Tom Gur, Ron D. Rothblum
2017 A conf
An Adaptivity Hierarchy Theorem for Property Testing.
CCC
Clément L. Canonne, Tom Gur
2017 J jnl
An Adaptivity Hierarchy Theorem for Property Testing.
CoRR
Clément L. Canonne, Tom Gur
2017 J jnl
An Adaptivity Hierarchy Theorem for Property Testing.
Electron. Colloquium Comput. Complex.
Clément L. Canonne, Tom Gur
2017 A conf
Distribution Testing Lower Bounds via Reductions from Communication Complexity.
CCC
Eric Blais, Clément L. Canonne, Tom Gur
2017 J jnl
Proofs of Proximity for Distribution Testing.
Electron. Colloquium Comput. Complex.
Alessandro Chiesa, Tom Gur
2017 J jnl
Relaxed Locally Correctable Codes.
Electron. Colloquium Comput. Complex.
Tom Gur, Govind Ramnarayan, Ron Rothblum
2016 J jnl
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.).
Electron. Colloquium Comput. Complex.
Eric Blais, Clément Louis Canonne, Tom Gur
2016 J jnl
Universal Locally Testable Codes.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur
2016 J jnl
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur
2015 J jnl
Arthur-Merlin streaming complexity.
Inf. Comput.
Tom Gur, Ran Raz
2015 A conf
Non-Interactive Proofs of Proximity.
ITCS
Tom Gur, Ron D. Rothblum
2015 — conf
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract).
ICALP (1)
Oded Goldreich, Tom Gur, Ron D. Rothblum
2015 J jnl
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur, Ron Rothblum
2015 A conf
Strong Locally Testable Codes with Relaxed Local Decoders.
CCC
Oded Goldreich, Tom Gur, Ilan Komargodski
2014 J jnl
Strong Locally Testable Codes with Relaxed Local Decoders.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Tom Gur, Ilan Komargodski
2013 J jnl
Arthur-Merlin Streaming Complexity
CoRR
Tom Gur, Ran Raz
2013 — conf
Arthur-Merlin Streaming Complexity.
ICALP (1)
Tom Gur, Ran Raz
2013 J jnl
Arthur-Merlin Streaming Complexity.
Electron. Colloquium Comput. Complex.
Tom Gur, Ran Raz
2013 J jnl
Non-Interactive Proofs of Proximity.
Electron. Colloquium Comput. Complex.
Tom Gur, Ron Rothblum
2013 J jnl
Testing Booleanity and the Uncertainty Principle.
Chic. J. Theor. Comput. Sci.
Tom Gur, Omer Tamuz
2012 J jnl
Testing Booleanity and the Uncertainty Principle
CoRR
Tom Gur, Omer Tamuz
2012 J jnl
Testing Booleanity and the Uncertainty Principle.
Electron. Colloquium Comput. Complex.
Tom Gur, Omer Tamuz