Tom Gur

Publication Activity (10 Years)

Years Active: 2012-2024
Publications (10 Years): 81

Top Topics

Decoding Algorithm

Mathematical Proofs

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Tom Gur, Jack O'Connor, Nicholas Spooner
Perfect Zero-Knowledge PCPs for #P. CoRR (2024)
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
On the Power of Interactive Proofs for Learning. STOC (2024)
Wilfred Salmon, Sergii Strelchuk, Tom Gur
Provable Advantage in Quantum PAC Learning. COLT (2024)
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
On the Power of Interactive Proofs for Learning. CoRR (2024)
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
Streaming Zero-Knowledge Proofs. CCC (2024)
Tom Gur, Jack O'Connor, Nicholas Spooner
Perfect Zero-Knowledge PCPs for #P. STOC (2024)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
Distribution-Free Proofs of Proximity. CCC (2024)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA (2024)
Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
Information-theoretic generalization bounds for learning from quantum data. COLT (2024)
Tom Gur, Jack O'Connor, Nicholas Spooner
Perfect Zero-Knowledge PCPs for #P. IACR Cryptol. ePrint Arch. 2024 (2024)
Marcel Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification. SIAM J. Comput. 52 (6) (2023)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum
Distribution-Free Proofs of Proximity. CoRR (2023)
Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner
Proof-Carrying Data From Arithmetized Random Oracles. IACR Cryptol. ePrint Arch. 2023 (2023)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. SOSA (2023)
Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey
Streaming Zero-Knowledge Proofs. CoRR (2023)
Tom Gur, Wilfred Salmon, Sergii Strelchuk
Provable Advantage in Quantum PAC Learning. Electron. Colloquium Comput. Complex. (2023)
Matthias Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian
Information-theoretic generalization bounds for learning from quantum data. CoRR (2023)
Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner
Proof-Carrying Data from Arithmetized Random Oracles. EUROCRYPT (2) (2023)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum
Distribution-Free Proofs of Proximity. Electron. Colloquium Comput. Complex. (2023)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-case to average-case reductions via additive combinatorics. STOC (2022)
Marcel Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. Quantum 6 (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. 29 (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. Electron. Colloquium Comput. Complex. (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR (2022)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SIAM J. Comput. 51 (6) (2022)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. FOCS (2022)
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. J. ACM 69 (2) (2022)
Tom Gur, Noam Lifshitz, Siqi Liu
Hypercontractivity on high dimensional expanders. STOC (2022)
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. CoRR (2021)
Oded Goldreich, Tom Gur
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Theor. Comput. Sci. (2021)
Tom Gur, Oded Lachish
On the Power of Relaxed Local Decoding Algorithms. SIAM J. Comput. 50 (2) (2021)
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
Sublinear quantum algorithms for estimating von Neumann entropy. Electron. Colloquium Comput. Complex. 28 (2021)
Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler
Quantum Proofs of Proximity. Electron. Colloquium Comput. Complex. 28 (2021)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. FOCS (2021)
Tom Gur, Yang P. Liu, Ron D. Rothblum
An Exponential Separation Between MA and AM Proofs of Proximity. Comput. Complex. 30 (2) (2021)
Tom Gur, Noam Lifshitz, Siqi Liu
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces. CoRR (2021)
Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian
Sublinear quantum algorithms for estimating von Neumann entropy. CoRR (2021)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. CoRR (2021)
Tom Gur, Noam Lifshitz, Siqi Liu
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces. Electron. Colloquium Comput. Complex. 28 (2021)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. SODA (2021)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SODA (2020)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. IEEE Trans. Inf. Theory 66 (5) (2020)
Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. Electron. Colloquium Comput. Complex. 27 (2020)
Tom Gur, Oded Lachish
On the Power of Relaxed Local Decoding Algorithms. SODA (2020)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. CoRR (2020)
Tom Gur, Govind Ramnarayan, Ron Rothblum
Relaxed Locally Correctable Codes. Theory Comput. 16 (2020)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. CoRR (2020)
Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. Electron. Colloquium Comput. Complex. 27 (2020)
Tom Gur, Oded Lachish
A Lower Bound for Relaxed Locally Decodable Codes. CoRR (2019)
Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner
Linear-Size Constant-Query IOPs for Delegating Computation. IACR Cryptol. ePrint Arch. 2019 (2019)
Irit Dinur, Oded Goldreich, Tom Gur
Every Set in P Is Strongly Testable Under a Suitable Encoding. ITCS (2019)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. ACM Trans. Comput. Theory 11 (3) (2019)
Eric Blais, Clément L. Canonne, Tom Gur
Distribution Testing Lower Bounds via Reductions from Communication Complexity. ACM Trans. Comput. Theory 11 (2) (2019)
Tom Gur, Oded Lachish
A Lower Bound for Relaxed Locally Decodable Codes. Electron. Colloquium Comput. Complex. 26 (2019)
Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner
Linear-Size Constant-Query IOPs for Delegating Computation. TCC (2) (2019)
Tom Gur, Yang P. Liu, Ron D. Rothblum
An Exponential Separation Between MA and AM Proofs of Proximity. ICALP (2018)
Tom Gur, Ron D. Rothblum
Non-interactive proofs of proximity. Comput. Complex. 27 (1) (2018)
Clément L. Canonne, Tom Gur
An adaptivity hierarchy theorem for property testing. Comput. Complex. 27 (4) (2018)
Oded Goldreich, Tom Gur
Universal Locally Testable Codes. Chic. J. Theor. Comput. Sci. 2018 (2018)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. CoRR (2018)
Tom Gur, Yang P. Liu, Ron D. Rothblum
An Exponential Separation Between MA and AM Proofs of Proximity. Electron. Colloquium Comput. Complex. 25 (2018)
Alessandro Chiesa, Tom Gur
Proofs of Proximity for Distribution Testing. ITCS (2018)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. Electron. Colloquium Comput. Complex. 25 (2018)
Tom Gur, Govind Ramnarayan, Ron D. Rothblum
Relaxed Locally Correctable Codes. ITCS (2018)
Oded Goldreich, Tom Gur, Ron D. Rothblum
Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput. 261 (2018)
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. CoRR (2018)
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. FOCS (2018)
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. Electron. Colloquium Comput. Complex. 25 (2018)
Irit Dinur, Oded Goldreich, Tom Gur
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. 25 (2018)
Clément L. Canonne, Tom Gur
An Adaptivity Hierarchy Theorem for Property Testing. Computational Complexity Conference (2017)
Tom Gur, Govind Ramnarayan, Ron Rothblum
Relaxed Locally Correctable Codes. Electron. Colloquium Comput. Complex. 24 (2017)
Tom Gur, Ron D. Rothblum
A Hierarchy Theorem for Interactive Proofs of Proximity. ITCS (2017)
Eric Blais, Clément L. Canonne, Tom Gur
Distribution Testing Lower Bounds via Reductions from Communication Complexity. Computational Complexity Conference (2017)
Clément L. Canonne, Tom Gur
An Adaptivity Hierarchy Theorem for Property Testing. CoRR (2017)
Alessandro Chiesa, Tom Gur
Proofs of Proximity for Distribution Testing. Electron. Colloquium Comput. Complex. 24 (2017)
Clément L. Canonne, Tom Gur
An Adaptivity Hierarchy Theorem for Property Testing. Electron. Colloquium Comput. Complex. 24 (2017)
Oded Goldreich, Tom Gur
Universal Locally Testable Codes. Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Tom Gur
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. Electron. Colloquium Comput. Complex. 23 (2016)
Eric Blais, Clément Louis Canonne, Tom Gur
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.). Electron. Colloquium Comput. Complex. 23 (2016)
Oded Goldreich, Tom Gur, Ron Rothblum
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. Electron. Colloquium Comput. Complex. 22 (2015)
Tom Gur, Ron D. Rothblum
Non-Interactive Proofs of Proximity. ITCS (2015)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. Computational Complexity Conference (2015)
Tom Gur, Ran Raz
Arthur-Merlin streaming complexity. Inf. Comput. 243 (2015)
Oded Goldreich, Tom Gur, Ron D. Rothblum
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). ICALP (1) (2015)
Oded Goldreich, Tom Gur, Ilan Komargodski
Strong Locally Testable Codes with Relaxed Local Decoders. Electron. Colloquium Comput. Complex. 21 (2014)
Tom Gur, Ran Raz
Arthur-Merlin Streaming Complexity. ICALP (1) (2013)
Tom Gur, Omer Tamuz
Testing Booleanity and the Uncertainty Principle. Chic. J. Theor. Comput. Sci. 2013 (2013)
Tom Gur, Ron Rothblum
Non-Interactive Proofs of Proximity. Electron. Colloquium Comput. Complex. 20 (2013)
Tom Gur, Ran Raz
Arthur-Merlin Streaming Complexity CoRR (2013)
Tom Gur, Ran Raz
Arthur-Merlin Streaming Complexity. Electron. Colloquium Comput. Complex. 20 (2013)
Tom Gur, Omer Tamuz
Testing Booleanity and the Uncertainty Principle. Electron. Colloquium Comput. Complex. 19 (2012)
Tom Gur, Omer Tamuz
Testing Booleanity and the Uncertainty Principle CoRR (2012)