Adaptive Sparse Möbius Transforms for Learning Polynomials
Yigit Efe Erginbas
EECS Department, University of California, Berkeley
Technical Report No. UCB/EECS-2026-19
April 30, 2026
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2026/EECS-2026-19.pdf
We consider the problem of exactly learning an s-sparse real-valued Boolean polynomial of degree d of the form f: {0, 1}n → ℝ. This problem corresponds to decomposing functions in the AND basis and is known as taking a Möbius transform. While the analogous problem for the parity basis (Fourier transform), f: {−1, 1}n → ℝ, is well-understood, the AND basis presents a unique challenge: the basis vectors are coherent, precluding standard compressed sensing methods. We overcome this challenge by identifying that we can exploit adaptive group testing to provide a constructive, query-efficient implementation of the Möbius transform (also known as Möbius inversion) for sparse functions.
We present two algorithms based on this insight. The Fully-Adaptive Sparse Möbius Transform (FASMT) uses O(sd log(n/d)) adaptive queries in O((sd + n) sd log(n/d)) time, which we show is near-optimal in query complexity. Furthermore, we also present the Partially-Adaptive Sparse Möbius Transform (PASMT), which uses O(sd2 log n) queries, trading a factor of d to reduce the number of adaptive rounds to O(d2 log n), with no dependence on s.
When applied to hypergraph reconstruction from edge-count queries, our results improve upon baselines by avoiding the combinatorial explosion in the rank d. We demonstrate the practical utility of our method for hypergraph reconstruction by applying it to learning real hypergraphs in simulations.
Advisors: Kannan Ramchandran and Thomas Courtade
BibTeX citation:
@mastersthesis{Erginbas:EECS-2026-19,
Author= {Erginbas, Yigit Efe},
Editor= {Ramchandran, Kannan and Courtade, Thomas},
Title= {Adaptive Sparse Möbius Transforms for Learning Polynomials},
School= {EECS Department, University of California, Berkeley},
Year= {2026},
Month= {Apr},
Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2026/EECS-2026-19.html},
Number= {UCB/EECS-2026-19},
Note= {This thesis is based on Yigit Efe Erginbas, Justin Singh Kang, Elizabeth Polito, and Kannan Ramchandran. Adaptive sparse Möbius transforms for learning polynomials, 2026. URL https://arxiv.org/abs/2602.06246},
Abstract= {<p>We consider the problem of exactly learning an <i>s</i>-sparse real-valued Boolean polynomial of degree <i>d</i> of the form <i>f</i>: {0, 1}<sup><i>n</i></sup> → ℝ. This problem corresponds to decomposing functions in the AND basis and is known as taking a <em>Möbius transform</em>. While the analogous problem for the <em>parity</em> basis (Fourier transform), <i>f</i>: {−1, 1}<sup><i>n</i></sup> → ℝ, is well-understood, the AND basis presents a unique challenge: the basis vectors are coherent, precluding standard compressed sensing methods. We overcome this challenge by identifying that we can exploit adaptive group testing to provide a constructive, query-efficient implementation of the Möbius transform (also known as Möbius inversion) for sparse functions.</p>
<p>We present two algorithms based on this insight. The <em>Fully-Adaptive Sparse Möbius Transform</em> (FASMT) uses <i>O</i>(<i>sd</i> log(<i>n</i>/<i>d</i>)) adaptive queries in <i>O</i>((<i>sd</i> + <i>n</i>) <i>sd</i> log(<i>n</i>/<i>d</i>)) time, which we show is near-optimal in query complexity. Furthermore, we also present the <em>Partially-Adaptive Sparse Möbius Transform</em> (PASMT), which uses <i>O</i>(<i>sd</i><sup>2</sup> log <i>n</i>) queries, trading a factor of <i>d</i> to reduce the number of adaptive rounds to <i>O</i>(<i>d</i><sup>2</sup> log <i>n</i>), with no dependence on <i>s</i>.</p>
<p>When applied to hypergraph reconstruction from <em>edge-count queries</em>, our results improve upon baselines by avoiding the combinatorial explosion in the rank <i>d</i>. We demonstrate the practical utility of our method for hypergraph reconstruction by applying it to learning real hypergraphs in simulations.</p>},
}
EndNote citation:
%0 Thesis %A Erginbas, Yigit Efe %E Ramchandran, Kannan %E Courtade, Thomas %T Adaptive Sparse Möbius Transforms for Learning Polynomials %I EECS Department, University of California, Berkeley %D 2026 %8 April 30 %@ UCB/EECS-2026-19 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2026/EECS-2026-19.html %F Erginbas:EECS-2026-19