The Axiotis-Sviridenko Condition-Number Conjecture
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. Their conjectured lower bound is established 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.
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Approximation algorithms
- Posed by
- Kyriakos Axiotis, Maxim Sviridenko
- Year posed
- 2021
- Years open
- 5y
- Solved
- 2026-08-03
- Model
- Gemini-based agentic system (internal)
- Vendor
- Collaborators
- Honghao Lin, Vahab Mirrokni, David P. Woodruff
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Conditional on the randomized exact-volume Small-Set Expansion Hypothesis, and stated for least-squares objectives rather than sparse convex optimization in general.
What the AI did
The acknowledgements state that the proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google, with the authors verifying it and editing for presentation.
Verification
arXiv preprint, not yet peer-reviewed.
Source
arXiv:2608.02588 - The Condition-Number Barrier in Sparse Least Squares