A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1{\}}^n$ under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability $\sigma \in (0,1\mathrm{/}2)$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log (1\mathrm{/}\epsilon )\mathrm{/}\sigma )})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\mathrm{\Omega }(\log (1+\sigma \mathrm{/}{\epsilon }^2)\mathrm{/}\sigma )}$. This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.