Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
The paper studies how many random samples are needed for Gaussian regression when the true model is a known low-degree subspace of functions on a Boolean cube. It finds that noise imposes an exponential cost, requiring significantly more samples than noiseless identification. It sharpens uncertainty principles to quantify this noise cost and constructs specific sets where functions concentrate their energy.