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

Tim Sinen

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 independent…