A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
arXiv:2605.02350v1 Announce Type: new
Abstract: We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under the uniform distribution in the model of \citet{KM25} where each input coordinate is independently flipped with …