{"id":"arxiv/2608.00451","url":"https://arxiv.org/abs/2608.00451","tags":["cs.DS","math.CO"],"score":0,"title":"Learning Latent Algebraic Structure from Ambiguous Set Observations","domain":"cs.DS","source":"arxiv","authors":["Cheng Peng"],"reviews":0,"subject":"cs.DS","summary":"We study when statistically learnable latent structure can also be recovered efficiently, and how membership queries change the answer. An unknown support $A\\subseteq\\mathbb F_2^n$ has small additive doubling and is observed through a fixed set $B$ satisfying $|A\\triangle B|\\leη|A|$. We seek one linear subspace $V$ such that every compatible support $A$ is covered by few $V$-cosets and satisfies $|V|\\le|A|$. For every $η<1$, polynomially many uniform samples suffice statistically, with cost polynomial in the doubling constant and proportional to $(1-η)^{-1}$; this radius dependence is sharp.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-01","reactions":{}}