Google用Gemini自动化系统先跑通了证明，人工再验证。你要是做稀疏优化或条件数相关算法，看看这个下界怎么证的。
arXiv:2608.02588 的论文证明了稀疏最小二乘问题的一个条件数下界：在随机化精确体积小集扩张假设（Small-Set Expansion Hypothesis）下，对任意固定的 γ∈(0,1]，不存在多项式时间随机算法能以至少 2/3 概率返回满足误差不超过最优值加 ε、且稀疏度 s=O(k·κ_{s+k}^{1-γ}) 的解。该结果甚至对有理数实例、A 为列满秩时也成立。作者表示，证明最初由 Google 内部开发的基于 Gemini 的自动化智能体系统完成，随后由人工验证并整理。
The Condition-Number Barrier in Sparse Least Squares
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 $γ\in(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 x\rVert_0$, \[ \lVert Ax-b\rVert_2^2 \leq \min_{\lVert z\rVert_0\leq k}\lVert Az-b\rVert_2^2+\varepsilon \quad\text{and}\quad s=O\!\left(k\,κ_{s+k}^{\,1-γ}\right), \] where $κ_r$ 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.