List-Decodable Regression via Expander Sketching

We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log (1\mathrm{/}\delta ))\mathrm{/}\alpha )$, list size $O(1\mathrm{/}\alpha )$, and near input-sparsity running time $\tilde{O}(\mathrm{n}\mathrm{n}\mathrm{z}(X)+d^3\mathrm{/}\alpha )$ 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.