4 citations · 17 across the 23 of their papers we have counts for
12 papers · 1 filter
3-Query RLDCs are Strictly Stronger than 3-Query LDCs
Tom Gur, Dor Minzer, Guy Weissenberg +1
We construct -query relaxed locally decodable codes (RLDCs) with constant alphabet size and length for -bit messages. Combined with the lower bound of $\tild…
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
Guy Goldberg, Tom Gur, Sidhant Saraogi
We show a nearly optimal lower bound on the length of linear relaxed locally decodable codes (RLDCs). Specifically, we prove that any -query linear RLDC $C\colon \{0,1\}^k \to \…
A Zero-Knowledge PCP Theorem
Tom Gur, Jack O'Connor, Nicholas Spooner
We show that for every polynomial q* there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at…
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh +3
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 l…
Perfect Zero-Knowledge PCPs for #P
Tom Gur, Jack O'Connor, Nicholas Spooner
We construct perfect zero-knowledge probabilistically checkable proofs (PZK-PCPs) for every language in #P. This is the first construction of a PZK-PCP for any language outside BPP…
Distribution-Free Proofs of Proximity
Hugo Aaronson, Tom Gur, Ninad Rajgopal +1
Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting where the algorithmic task is to accept function…