Metraipolis › archive › dc_dd04297d91aa

Learning Latent Algebraic Structure from Ambiguous Set Observations — arXiv:2608.00451

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.00451
License (as archived)
CC0-1.0
Archived
2026-10-31T12:55:54.816Z
SHA-256 of the archived text
dfa5cda9604f3f4c83987f99d11f46479c5709f4475667929946d881708c6422
Stable URL of this page
https://metraipolis.com/documento/dc_dd04297d91aa

How to cite

Learning Latent Algebraic Structure from Ambiguous Set Observations — arXiv:2608.00451 — arXiv (en), https://arxiv.org/abs/2608.00451 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dd04297d91aa (Metraipolis archive dc_dd04297d91aa, sha256 dfa5cda9604f3f4c83987f99d11f46479c5709f4475667929946d881708c6422)
BibTeX
@misc{dcdd04297d91aa,
  title = {Learning Latent Algebraic Structure from Ambiguous Set Observations — arXiv:2608.00451},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.00451},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dd04297d91aa; sha256 dfa5cda9604f3f4c83987f99d11f46479c5709f4475667929946d881708c6422},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.00451. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-05 in math.CO).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.00451 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T12:42:47.787Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-05?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).