![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Tom Gur
Person information
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c28]Graham Cormode, Marcel Dall'Agnol, Tom Gur
, Chris Hickey:
Streaming Zero-Knowledge Proofs. CCC 2024: 2:1-2:66 - [c27]Hugo Aaronson, Tom Gur
, Ninad Rajgopal, Ron D. Rothblum:
Distribution-Free Proofs of Proximity. CCC 2024: 24:1-24:18 - [c26]Matthias C. Caro, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian:
Information-theoretic generalization bounds for learning from quantum data. COLT 2024: 775-839 - [c25]Wilfred Salmon, Sergii Strelchuk, Tom Gur:
Provable Advantage in Quantum PAC Learning. COLT 2024: 4487-4510 - [c24]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA 2024: 2535-2567 - [c23]Tom Gur
, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal
, Bahar Salamatian, Igor Shinkar:
On the Power of Interactive Proofs for Learning. STOC 2024: 1063-1070 - [c22]Tom Gur
, Jack O'Connor
, Nicholas Spooner
:
Perfect Zero-Knowledge PCPs for #P. STOC 2024: 1724-1730 - [i48]Tom Gur, Jack O'Connor, Nicholas Spooner:
Perfect Zero-Knowledge PCPs for #P. CoRR abs/2403.11941 (2024) - [i47]Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar:
On the Power of Interactive Proofs for Learning. CoRR abs/2404.08158 (2024) - [i46]Tom Gur, Jack O'Connor, Nicholas Spooner:
Perfect Zero-Knowledge PCPs for #P. IACR Cryptol. ePrint Arch. 2024: 462 (2024) - 2023
- [j17]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): 1413-1463 (2023) - [c21]Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner:
Proof-Carrying Data from Arithmetized Random Oracles. EUROCRYPT (2) 2023: 379-404 - [c20]Alexander Golovnev, Tom Gur
, Igor Shinkar:
Derandomization of Cell Sampling. SOSA 2023: 278-284 - [i45]Graham Cormode, Marcel Dall'Agnol, Tom Gur, Chris Hickey:
Streaming Zero-Knowledge Proofs. CoRR abs/2301.02161 (2023) - [i44]Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron D. Rothblum:
Distribution-Free Proofs of Proximity. CoRR abs/2308.08874 (2023) - [i43]Matthias C. Caro
, Tom Gur, Cambyse Rouzé, Daniel Stilck França, Sathyawageeswar Subramanian:
Information-theoretic generalization bounds for learning from quantum data. CoRR abs/2311.05529 (2023) - [i42]Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum:
Distribution-Free Proofs of Proximity. Electron. Colloquium Comput. Complex. TR23 (2023) - [i41]Tom Gur, Wilfred Salmon, Sergii Strelchuk:
Provable Advantage in Quantum PAC Learning. Electron. Colloquium Comput. Complex. TR23 (2023) - [i40]Megan Chen, Alessandro Chiesa, Tom Gur, Jack O'Connor, Nicholas Spooner:
Proof-Carrying Data From Arithmetized Random Oracles. IACR Cryptol. ePrint Arch. 2023: 587 (2023) - 2022
- [j16]Alessandro Chiesa
, Michael A. Forbes, Tom Gur
, Nicholas Spooner
:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. J. ACM 69(2): 15:1-15:44 (2022) - [j15]Marcel Dall'Agnol, Tom Gur
, Subhayan Roy Moulik
, Justin Thaler:
Quantum Proofs of Proximity. Quantum 6: 834 (2022) - [j14]Alessandro Chiesa, Tom Gur
, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SIAM J. Comput. 51(6): 1839-1865 (2022) - [c19]Tom Gur
, Noam Lifshitz, Siqi Liu:
Hypercontractivity on high dimensional expanders. STOC 2022: 176-184 - [c18]Vahid R. Asadi, Alexander Golovnev, Tom Gur
, Igor Shinkar:
Worst-case to average-case reductions via additive combinatorics. STOC 2022: 1566-1574 - [i39]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR abs/2202.08996 (2022) - [i38]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR abs/2212.03348 (2022) - [i37]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. TR22 (2022) - [i36]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. TR22 (2022) - 2021
- [j13]Tom Gur
, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. Comput. Complex. 30(2): 12 (2021) - [j12]Tom Gur
, Oded Lachish
:
On the Power of Relaxed Local Decoding Algorithms. SIAM J. Comput. 50(2): 788-813 (2021) - [j11]Oded Goldreich, Tom Gur
:
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP. Theor. Comput. Sci. 878-879: 83-101 (2021) - [c17]Srinivasan Arunachalam, Alex B. Grilo, Tom Gur
, Igor C. Oliveira, Aarthi Sundaram:
Quantum learning algorithms imply circuit lower bounds. FOCS 2021: 562-573 - [c16]Marcel de Sena Dall'Agnol
, Tom Gur
, Oded Lachish
:
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. SODA 2021: 1651-1665 - [i35]Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. CoRR abs/2105.03697 (2021) - [i34]Alexander Golovnev, Tom Gur, Igor Shinkar:
Derandomization of Cell Sampling. CoRR abs/2108.05970 (2021) - [i33]Tom Gur, Noam Lifshitz, Siqi Liu:
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for ε-Product Spaces. CoRR abs/2111.09375 (2021) - [i32]Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian:
Sublinear quantum algorithms for estimating von Neumann entropy. CoRR abs/2111.11139 (2021) - [i31]Marcel de Sena Dall'Agnol, Tom Gur, Subhayan Roy Moulik, Justin Thaler:
Quantum Proofs of Proximity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i30]Tom Gur, Min-Hsiu Hsieh, Sathyawageeswar Subramanian:
Sublinear quantum algorithms for estimating von Neumann entropy. Electron. Colloquium Comput. Complex. TR21 (2021) - [i29]Tom Gur, Noam Lifshitz, Siqi Liu:
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j10]Tom Gur
, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. IEEE Trans. Inf. Theory 66(5): 2904-2911 (2020) - [j9]Tom Gur, Govind Ramnarayan, Ron Rothblum:
Relaxed Locally Correctable Codes. Theory Comput. 16: 1-68 (2020) - [c15]Tom Gur
, Oded Lachish:
On the Power of Relaxed Local Decoding Algorithms. SODA 2020: 1377-1394 - [c14]Alessandro Chiesa, Tom Gur
, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SODA 2020: 1395-1411 - [i28]Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish:
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. CoRR abs/2010.04985 (2020) - [i27]Srinivasan Arunachalam, Alex B. Grilo, Tom Gur
, Igor C. Oliveira, Aarthi Sundaram:
Quantum learning algorithms imply circuit lower bounds. CoRR abs/2012.01920 (2020) - [i26]Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram:
Quantum learning algorithms imply circuit lower bounds. Electron. Colloquium Comput. Complex. TR20 (2020) - [i25]Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. Electron. Colloquium Comput. Complex. TR20 (2020) - [i24]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. TR20 (2020)
2010 – 2019
- 2019
- [j8]Eric Blais, Clément L. Canonne
, Tom Gur
:
Distribution Testing Lower Bounds via Reductions from Communication Complexity. ACM Trans. Comput. Theory 11(2): 6:1-6:37 (2019) - [j7]Oded Goldreich, Tom Gur
, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. ACM Trans. Comput. Theory 11(3): 17:1-17:38 (2019) - [c13]Irit Dinur
, Oded Goldreich, Tom Gur:
Every Set in P Is Strongly Testable Under a Suitable Encoding. ITCS 2019: 30:1-30:17 - [c12]Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur
, Michael Riabzev, Nicholas Spooner:
Linear-Size Constant-Query IOPs for Delegating Computation. TCC (2) 2019: 494-521 - [i23]Tom Gur, Oded Lachish:
A Lower Bound for Relaxed Locally Decodable Codes. CoRR abs/1904.08112 (2019) - [i22]Tom Gur, Oded Lachish:
A Lower Bound for Relaxed Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR19 (2019) - [i21]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: 1230 (2019) - 2018
- [j6]Tom Gur
, Ron D. Rothblum:
Non-interactive proofs of proximity. Comput. Complex. 27(1): 99-207 (2018) - [j5]Clément L. Canonne
, Tom Gur
:
An adaptivity hierarchy theorem for property testing. Comput. Complex. 27(4): 671-716 (2018) - [j4]Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. Chic. J. Theor. Comput. Sci. 2018 (2018) - [j3]Oded Goldreich, Tom Gur
, Ron D. Rothblum:
Proofs of proximity for context-free languages and read-once branching programs. Inf. Comput. 261: 175-201 (2018) - [c11]Alessandro Chiesa, Michael A. Forbes, Tom Gur
, Nicholas Spooner
:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. FOCS 2018: 755-765 - [c10]Tom Gur, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. ICALP 2018: 73:1-73:15 - [c9]Tom Gur, Govind Ramnarayan, Ron D. Rothblum:
Relaxed Locally Correctable Codes. ITCS 2018: 27:1-27:11 - [c8]Alessandro Chiesa, Tom Gur:
Proofs of Proximity for Distribution Testing. ITCS 2018: 53:1-53:14 - [i20]Tom Gur, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. CoRR abs/1801.03200 (2018) - [i19]Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. CoRR abs/1803.01519 (2018) - [i18]Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner:
Spatial Isolation Implies Zero Knowledge Even in a Quantum World. Electron. Colloquium Comput. Complex. TR18 (2018) - [i17]Irit Dinur, Oded Goldreich, Tom Gur:
Every set in P is strongly testable under a suitable encoding. Electron. Colloquium Comput. Complex. TR18 (2018) - [i16]Tom Gur, Yang P. Liu, Ron D. Rothblum:
An Exponential Separation Between MA and AM Proofs of Proximity. Electron. Colloquium Comput. Complex. TR18 (2018) - [i15]Tom Gur, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c7]Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. CCC 2017: 27:1-27:25 - [c6]Eric Blais, Clément L. Canonne, Tom Gur:
Distribution Testing Lower Bounds via Reductions from Communication Complexity. CCC 2017: 28:1-28:40 - [c5]Tom Gur, Ron D. Rothblum:
A Hierarchy Theorem for Interactive Proofs of Proximity. ITCS 2017: 39:1-39:43 - [i14]Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. CoRR abs/1702.05678 (2017) - [i13]Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. Electron. Colloquium Comput. Complex. TR17 (2017) - [i12]Alessandro Chiesa, Tom Gur:
Proofs of Proximity for Distribution Testing. Electron. Colloquium Comput. Complex. TR17 (2017) - [i11]Tom Gur, Govind Ramnarayan, Ron Rothblum:
Relaxed Locally Correctable Codes. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i10]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. TR16 (2016) - [i9]Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. Electron. Colloquium Comput. Complex. TR16 (2016) - [i8]Oded Goldreich, Tom Gur:
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j2]Tom Gur
, Ran Raz
:
Arthur-Merlin streaming complexity. Inf. Comput. 243: 145-165 (2015) - [c4]Oded Goldreich
, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. CCC 2015: 1-41 - [c3]Oded Goldreich
, Tom Gur
, Ron D. Rothblum:
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs - (Extended Abstract). ICALP (1) 2015: 666-677 - [c2]Tom Gur
, Ron D. Rothblum:
Non-Interactive Proofs of Proximity. ITCS 2015: 133-142 - [i7]Oded Goldreich, Tom Gur, Ron Rothblum:
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [i6]Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j1]Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. Chic. J. Theor. Comput. Sci. 2013 (2013) - [c1]Tom Gur
, Ran Raz:
Arthur-Merlin Streaming Complexity. ICALP (1) 2013: 528-539 - [i5]Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. CoRR abs/1302.0418 (2013) - [i4]Tom Gur, Ran Raz:
Arthur-Merlin Streaming Complexity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i3]Tom Gur, Ron Rothblum:
Non-Interactive Proofs of Proximity. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [i2]Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. CoRR abs/1204.0944 (2012) - [i1]Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. Electron. Colloquium Comput. Complex. TR12 (2012)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 21:10 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint