Tom Gur

STOC Conference 2025 Conference Paper

A Zero-Knowledge PCP Theorem

• Tom Gur
• Jack O'Connor
• Nicholas Spooner

We show that for every polynomial 𝑞∗ there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at most 𝑞∗ queries to the proof. In addition, we construct exponential-size constant- query PCPs for NEXP with perfect zero knowledge against any polynomial-time adversary. This improves upon both a recent con- struction of perfect zero-knowledge PCPs for #P (STOC 2024) and the seminal work of Kilian, Petrank and Tardos (STOC 1997).

STOC Conference 2025 Conference Paper

Quantum Communication Advantage in TFNP

• Mika Göös
• Tom Gur
• Siddhartha Jain 0002
• Jiawei Li 0014

We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

STOC Conference 2024 Conference Paper

On the Power of Interactive Proofs for Learning

• Tom Gur
• Mohammad Mahdi Jahanara
• Mohammad Mahdi Khodabandeh
• Ninad Rajgopal
• Bahar Salamatian
• Igor Shinkar

We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. We construct an interactive protocol for learning the t largest Fourier characters of a given function f ∶ {0,1} n → {0,1} up to an arbitrarily small error, wherein the verifier uses poly ( t ) random examples. This improves upon the Interactive Goldreich-Levin protocol of Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) whose sample complexity is poly ( t , n ). For agnostically learning the class AC 0 [2] under the uniform distribution, we build on the work of Carmosino, Impagliazzo, Kabanets, and Kolokolova (APPROX/RANDOM 2017) and design an interactive protocol, where given a function f ∶ {0,1} n → {0,1}, the verifier learns the closest hypothesis up to polylog ( n ) multiplicative factor, using quasi-polynomially many random examples. In contrast, this class has been notoriously resistant even for constructing realisable learners (without a prover) using random examples. For agnostically learning k -juntas under the uniform distribution, we obtain an interactive protocol, where the verifier uses O (2 k ) random examples to a given function f ∶ {0,1} n → {0,1}. Crucially, the sample complexity of the verifier is independent of n . We also show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial. Specifically, we show a protocol for an arbitrary class C of Boolean functions in the distribution-free setting, where the verifier uses O (1) labeled examples to learn f .

STOC Conference 2024 Conference Paper

Perfect Zero-Knowledge PCPs for #P

• Tom Gur
• Jack O'Connor
• Nicholas Spooner

SODA Conference 2024 Conference Paper

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

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

STOC Conference 2022 Conference Paper

Hypercontractivity on high dimensional expanders

• Tom Gur
• Noam Lifshitz
• Siqi Liu 0005

STOC Conference 2022 Conference Paper

Worst-case to average-case reductions via additive combinatorics

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

We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O ( T ) that are correct on all inputs.

SODA Conference 2021 Conference Paper

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

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

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes q adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with sample complexity. We also prove that this transformation is nearly optimal, and admits a scheme for constructing privacy-preserving local algorithms. Using the unified view that our structural theorem provides, we obtain the following results. • We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020). • We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers. • We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation. Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal–Szemerédi theorem.

FOCS Conference 2021 Conference Paper

Quantum learning algorithms imply circuit lower bounds

• Srinivasan Arunachalam
• Alex Bredariol Grilo
• Tom Gur
• Igor C. Oliveira 0001
• Aarthi Sundaram

We establish the first general connection between the design of quantum algorithms and circuit lower bounds. Specifically, let $\mathfrak{C}$ be a class of polynomial-size concepts, and suppose that $\mathfrak{C}$ can be PAC-learned with membership queries under the uniform distribution with error $1/2 -\gamma$ by a time $T$ quantum algorithm. We prove that if $\gamma^{2}\cdot T \ll 2^{n} /n$, then $\mathsf{BQE}\not\subset \mathfrak{C}$, where $\mathsf{BQE} = \mathsf{BQTIME}[2^{O(n)}]$ is an exponential-time analogue of $\mathsf{BQP}$. This result is optimal in both $\gamma$ and $T$, since it is not hard to learn any class $\mathfrak{C}$ of functions in (classical) time $T=2^{n}$ (with no error), or in quantum time $T= \mathsf{poly}(n)$ with error at most $1/2-\Omega(2^{-n/2})$ via Fourier sampling. In other words, even a marginal quantum speedup over these generic learning algorithms would lead to major consequences in complexity lower bounds. As a consequence, our result shows that the study of quantum learning speedups is intimately connected to fundamental open problems about algorithms, quantum computing, and complexity theory. Our proof builds on several works in learning theory, pseudorandomness, and computational complexity, and on a connection between non-trivial classical learning algorithms and circuit lower bounds established by Oliveira and Santhanam (CCC 2017). Extending their approach to quantum learning algorithms turns out to create significant challenges, since extracting computational hardness from a quantum computation is inherently more complicated. To achieve that, we show among other results how pseudorandom generators imply learning-to-lower-bound connections in a generic fashion, construct the first conditional pseudorandom generator secure against uniform quantum computations, and extend the local list-decoding algorithm of Impagliazzo, Jaiswal, Kabanets and Wigderson (SICOMP 2010) to quantum circuits via a delicate analysis. We believe that these contributions are of independent interest and might find other applications.

TCS Journal 2021 Journal Article

Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP

• Oded Goldreich
• Tom Gur

Universal locally testable codes ( universal - LTC s), recently introduced in our companion paper (CJTCS, 2018), are codes that admit local tests for membership in numerous subcodes, allowing for testing properties of the encoded message. Unfortunately, universal - LTC s suffer strong limitations, which motivate us to initiate, in this work, the study of the “NP analogue” of these codes, wherein the testing procedures are also given free access to a short proof, akin the MA proofs of proximity of Gur and Rothblum (Computational Complexity 2018). We call such codes “universal locally verifiable codes” ( universal - LVC s). A universal - LVC C: { 0, 1 } k → { 0, 1 } η for a family of functions F = { f i: { 0, 1 } k → { 0, 1 } } i ∈ [ M ] is a code such that, for every i ∈ [ M ], membership in the subcode { C ( x ): f i ( x ) = 1 } can be verified locally using explicit access to a short (sublinear length) proof. A universal - LVC can be viewed as providing an encoding of inputs under which a large family of properties of the encoded inputs can be locally testable using a short proof. We show universal - LVC s of block length O ˜ ( n 2 ) for the family of all functions expressible by t-ary constraint satisfaction problems (t-CSP) over n constraints and k variables, with proof length and query complexity O ˜ ( n 2 / 3 ), where t = O ( 1 ) and n ≥ k. In addition, we prove a lower bound of p ⋅ q = Ω ˜ ( k ) for every polynomial length universal - LVC, having proof complexity p and query complexity q, for such CSP functions. We give an application of universal - LVC s for interactive proofs of proximity ( IPP ), introduced by Rothblum, Vadhan, and Wigderson (STOC 2013), which are interactive proof systems wherein the verifier queries only a sublinear number of input bits to the end of asserting that, with high probability, the input is close to an accepting input. Specifically, we show a 3-round IPP for the set of assignments that satisfy fixed CSP instances, with sublinear communication and query complexity, which we derive from our universal - LVC for CSP functions.

SODA Conference 2020 Conference Paper

On the Power of Relaxed Local Decoding Algorithms

• Tom Gur
• Oded Lachish

A locally decodable code (LDC) C: {0, 1} k → {0, 1} n is an error correcting code that admits algorithms for recovering individual bits of the message by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to distributed storage. However, despite nearly two decades of extensive study, the best known constructions of LDCs with O (1)-query decoding algorithms have super-polynomial blocklength. The notion of relaxed LDCs is a natural relaxation of LDCs, which aims to bypass the foregoing barrier by requiring local decoding of nearly all individual message bits, yet allowing decoding failure (but not error) on the rest. State of the art constructions of O (1)-query relaxed LDCs achieve blocklength n = O ( k 1+ γ ) for an arbitrarily small constant γ. Using algorithmic and combinatorial techniques, we prove an impossibility result, showing that codes with blocklength n = k 1+o(1) cannot be relaxed decoded with O (1)-query algorithms. This resolves an open problem raised by Goldreich in 2004.

SODA Conference 2020 Conference Paper

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

• Alessandro Chiesa
• Tom Gur
• Igor Shinkar

Locally correctable codes (LCCs) are codes C: Σ k → Σ n which admit local algorithms that can correct any individual symbol of a corrupted codeword via a minuscule number of queries. One of the central problems in algorithmic coding theory is to construct O (1)-query LCC with minimal block length. Alas, state-of-the-art of such codes requires exponential block length to admit O (1)-query algorithms for local correction, despite much attention during the last two decades. This lack of progress prompted the study of relaxed LCCs, which allow the correction algorithm to abort (but not err) on small fraction of the locations. This relaxation turned out to allow constant-query correction algorithms for codes with polynomial block length. Specifically, prior work showed that there exist O (1)-query relaxed LCCs that achieve nearly-quartic block length n = k 4+ α, for an arbitrarily small constant α > 0. We construct an O (1)-query relaxed LCC with nearly-linear block length n = k 1+ α, for an arbitrarily small constant α > 0. This significantly narrows the gap between the lower bound which states that there are no O (1)-query relaxed LCCs with block length n = k 1+ o (1). In particular, this resolves an open problem raised by Gur, Ramnarayan, and Rothblum (ITCS 2018).

I&C Journal 2018 Journal Article

Proofs of proximity for context-free languages and read-once branching programs

• Oded Goldreich
• Tom Gur
• Ron D. Rothblum

Proofs of proximity are proof systems wherein the verifier queries a sublinear number of bits, and soundness only asserts that inputs that are far from valid will be rejected. In their minimal form, called MA proofs of proximity ( MAP ), the verifier receives, in addition to query access to the input, also free access to a short (sublinear) proof. A more general notion is that of interactive proofs of proximity ( IPP ), wherein the verifier is allowed to interact with an omniscient, yet untrusted prover. We construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are: 1. MAP s for these two classes, in which, for inputs of length n, both the verifier's query complexity and the length of the MAP proof are O ˜ ( n ). 2. IPP s for the same two classes with constant query complexity, poly-logarithmic communication complexity, and logarithmically many rounds of interaction.

FOCS Conference 2018 Conference Paper

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

• Alessandro Chiesa
• Michael A. Forbes 0001
• Tom Gur
• Nicholas Spooner

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP* model captures this setting. In this work we study the following question: does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP*. Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.

I&C Journal 2015 Journal Article

Arthur–Merlin streaming complexity

• Tom Gur
• Ran Raz

We study the power of Arthur–Merlin probabilistic proof systems in the data stream model. We show a canonical AM streaming algorithm for a class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it. As an application, we give an AM streaming algorithm for the Distinct Elements problem. Given a data stream of length m over alphabet of size n, the algorithm uses O ˜ ( s ) space and a proof of size O ˜ ( w ), for every s, w such that s ⋅ w ≥ n (where O ˜ hides a polylog ( m, n ) factor). We also prove a lower bound, showing that every MA streaming algorithm for the Distinct Elements problem that uses s bits of space and a proof of size w, satisfies s ⋅ w = Ω ( n ). Furthermore, the lower bound also holds for approximating the number of distinct elements within a multiplicative factor of 1 ± 1 / n. As a part of the proof of the lower bound for the Distinct Elements problem, we show a new lower bound of Ω ( n ) on the MA communication complexity of the Gap Hamming Distance problem, and prove its tightness.