Adaptive Sparse Möbius Transforms for Learning Polynomials
Yigit Efe Erginbas Justin Singh Kang Elizabeth Polito Kannan Ramchandran · 2026
Read Adaptive Sparse Möbius Transforms for Learning Polynomials by Yigit Efe Erginbas Justin Singh Kang Elizabeth Polito Kannan Ramchandran (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-06246.txt.
Description
Learning a sparse polynomial over yes-or-no variables, exactly and with few questions, is the problem tackled by Yigit Efe Erginbas and 3 co-authors. Writing such a function in the AND basis is called a Möbius transform. The parity basis version is well understood, but AND basis vectors overlap too much for standard compressed sensing tricks.
The team turns adaptive group testing, a method for finding rare items with pooled tests, into a working transform. Their fully adaptive version asks close to the fewest possible questions. A partly adaptive variant trades some extra questions for far fewer rounds of adaptivity. The methods also speed up rebuilding hypergraphs from edge-count questions.
Catalog record
| CREATOR | Yigit Efe Erginbas Justin Singh Kang Elizabeth Polito Kannan Ramchandran |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-06246