Tom Gur

Available identifiers

List of research outcomes

Publication	Date of Publication	Type
Quantum worst-case to average-case reductions for all linear problems	2024-11-28	Paper
Derandomization of cell sampling	2024-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q6147355	2024-01-15	Paper
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification	2023-12-19	Paper
Hypercontractivity on high dimensional expanders	2023-12-08	Paper
Worst-case to average-case reductions via additive combinatorics	2023-12-08	Paper
Proof-carrying data from arithmetized random oracles	2023-12-08	Paper
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	2023-04-04	Paper
Every Set in P Is Strongly Testable Under a Suitable Encoding	2022-07-18	Paper
Spatial Isolation Implies Zero Knowledge Even in a Quantum World	2022-03-31	Paper
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\varepsilon$-Product Spaces	2021-11-17	Paper
Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP	2021-07-22	Paper
Relaxed Locally Correctable Codes	2021-06-15	Paper
Proofs of Proximity for Distribution Testing	2021-06-15	Paper
On the Power of Relaxed Local Decoding Algorithms	2021-05-27	Paper
https://portal.mardi4nfdi.de/entity/Q5857610	2021-04-01	Paper
On the Power of Relaxed Local Decoding Algorithms	2021-02-02	Paper
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity	2021-02-02	Paper
An Entropy Lower Bound for Non-Malleable Extractors	2020-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q5111157	2020-05-26	Paper
https://portal.mardi4nfdi.de/entity/Q5111158	2020-05-26	Paper
Linear-size constant-query IOPs for delegating computation	2020-04-30	Paper
Strong Locally Testable Codes with Relaxed Local Decoders	2019-12-16	Paper
Distribution Testing Lower Bounds via Reductions from Communication Complexity	2019-12-16	Paper
A Lower Bound for Relaxed Locally Decodable Codes	2019-04-17	Paper
An adaptivity hierarchy theorem for property testing	2018-12-10	Paper
https://portal.mardi4nfdi.de/entity/Q4578332	2018-08-08	Paper
Proofs of proximity for context-free languages and read-once branching programs	2018-06-14	Paper
A Hierarchy Theorem for Interactive Proofs of Proximity	2018-05-03	Paper
Non-interactive proofs of proximity	2018-04-18	Paper
https://portal.mardi4nfdi.de/entity/Q4601820	2018-01-24	Paper
Non-Interactive Proofs of Proximity	2017-05-19	Paper
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs	2015-10-27	Paper
Arthur-Merlin streaming complexity	2015-06-09	Paper
https://portal.mardi4nfdi.de/entity/Q5414633	2014-05-07	Paper
Arthur-Merlin Streaming Complexity	2013-08-06	Paper

Research outcomes over time

This page was built for person: Tom Gur