Robust Polynomial Freiman-Ruzsa from Corrupted Set Observations

Abstract

We study structural recovery from an exact but adversarially corrupted set observation over ${\mathbb{F}}_2^n$. A hidden nonempty set $A$ satisfies $|A+A|\le K|A|$, while the algorithm receives deterministic membership access and independent exact uniform samples only from a set $B$ satisfying $|A△B|\le \eta |A|$. For $\eta \le c{K}^{-1/2}$, we give a randomized FPT-form algorithm which, with high probability, outputs a subspace $V$ satisfying $|V|\le |A|$ and ${\mathcal{N}}_V(A)\le K^{O(1)}$. For every supplied $\eta <1$, writing $\epsilon =1-\eta$, we also give an observation-only algorithm that outputs $O(\sqrt{K}{\epsilon }^{-2}\log (3/\epsilon ))$ subspaces. For every hidden set compatible with $B,K,\eta$, some list entry has size at most that hidden set and covering number $\mathrm{poly}(K,{\epsilon }^{-1})$. The sample complexity is polynomial, while the direct query and running-time bounds are XP. Every nonempty compatibility class also admits, nonconstructively, one common subspace $V$ such that $|V|\le |A|$ and ${\mathcal{N}}_V(A)\le 2K(1-\eta {)}^{-1}{P}_{\mathrm{PFR}}(K)$ simultaneously for every compatible hidden set $A$. An exact two-subspace construction forces common covering cost $\Theta ((1-\eta {)}^{-1/2})$, leaving quantitative and algorithmic list-to-single gaps. We further show that the $K^{-1/2}$ contamination scale is optimal up to constants for the one-core, size-only lifting mechanism used in the single-output argument. The proofs combine a persistent randomized Balog-Szemerédi-Gowers procedure producing a fixed implicit small-doubling subset on the $\sqrt{\alpha }$ retained-mass scale, conditionally exact finite product sampling, size-oblivious algorithmic PFR, and deterministic lifting.