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\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.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.00451
curl -X POST /api/v1/records/arxiv/2608.00451/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.00451/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'