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

CREATORYigit Efe Erginbas Justin Singh Kang Elizabeth Polito Kannan Ramchandran
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-06246

Browse the full library · About the Tower of Babel