Exact Fourier-Sparse Recovery over Hypercube : Simpler and Stronger

We study the problem of exact recovery of Fourier-sparse functions over the Boolean hypercube ${\mathbb{F}}_2^n$, a fundamental problem at the intersection of learning theory, signal processing, and inverse problems. Given oracle access to such a function whose Fourier spectrum is supported on at most \(k\) coefficients, the goal is to identify all nonzero Fourier coefficients exactly using as few queries as possible. An \(\Omega(nk)\) query lower bound is known for this problem, which also implies an \(\Omega(nk)\) lower bound on the running time. Recent works have made significant progress, developing algorithms whose query and time complexities are within polylogarithmic factors of these lower bounds. However, these algorithms often rely on relatively sophisticated machinery, making the underlying recovery process less transparent. In this work, we present a randomized algorithm that achieves polylogarithmic improvements over the best known results, while being substantially simpler in its design. Our algorithm uses \(O(nk)\) queries and \(O(nk\log k)\) time, making it sample-optimal up to constant factors, with running time within an \(O(\log k)\) factor of the corresponding lower bound. Beyond these quantitative improvements, we believe our approach enables a substantially simpler and more transparent recovery framework, which may prove useful in broader sparse-recovery settings.