List-Decodable Regression via Expander Sketching

We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity tildeO((d+log(1/δ))/α), list size O(1/α), and near input-sparsity running time tildeO(nnz(X)+d3/α) under standard sub-Gaussian assumptions. Our method uses lossless expanders to synthesize lightly contaminated batches, enabling robust aggregation and a short spectral filtering stage that matches the best known efficient guarantees while avoiding SoS machinery and explicit batch structure.