# The Condition-Number Barrier in Sparse Least Squares

arXiv: https://arxiv.org/abs/2608.02588 · HTML: https://mlsanity.com/paper/2608.02588/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 11 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Builds on (most cited first, 3 of 3)

- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Sparse Convex Optimization via Adaptively Regularized Hard Thresholding](https://mlsanity.com/paper/2006.14571/) (2020)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)

## Built on by (most cited first, 1 of 1)

- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)

## Abstract (arXiv)

In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in sparse convex optimization cannot be improved by a polynomial-time algorithm. We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis in the weighted regular-graph formulation of Raghavendra, Steurer, and Tulsiani [RST12]. Concretely, for every fixed γ∈(0,1], there is no randomized polynomial-time algorithm that, with probability at least 2/3, returns a vector x such that, writing s=lVert xrVert0, [ lVert Ax-brVert22 ≤ minlVert zrVert0≤ klVert Az-brVert22+varepsilon quadandquad s=O!left(k,kappas+k,1-γright), ] where kappar is the restricted condition number at sparsity level r. The result holds even on rational instances with A of full column rank. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.