Robust Polynomial Freiman-Ruzsa from Corrupted Set Observations

Cheng Peng

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 algorit…