The Axiotis-Sviridenko Condition-Number Conjecture
Statement
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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
Gemini-based agentic system (internal), with Honghao Lin, Vahab Mirrokni and David P. WoodruffThe record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.
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.
Conditional on the randomized exact-volume Small-Set Expansion Hypothesis, and stated for least-squares objectives rather than sparse convex optimization in general.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.