Learning Latent Algebraic Structure from Ambiguous Set Observations

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△B|\le \eta |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 $\eta <1$, polynomially many uniform samples suffice statistically, with cost polynomial in the doubling constant and proportional to $(1-\eta {)}^{-1}$; this radius dependence is sharp. Under a specified hardness assumption for learning parities with noise (search-LPN), however, no polynomial-time sample-only learner achieves even constant covering cost, including when the latent support is unique. At fixed structural parameters and the same constant covering budget, adding exact membership queries to $B$ permits polynomial-time recovery. The general query learner constructs a short structural list and uses fresh samples to select one common output through a majority-coverage rule. Persistent structured cores make this candidate construction possible. At doubling one, a complementary distinction appears at $\eta =1/3$: coarse recovery remains polynomial time, while exact recovery requires exponentially many accesses in the worst case when latent cardinality is unknown.