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

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

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.