VibeMathedMath problems solved by AI
All problems

Avidor-Zwick Question on Low-Dimensional Max-Cut SDP

For fixed dd, can every dd-dimensional feasible solution of the triangle-strengthened Max-Cut SDP be rounded in polynomial time with ratio strictly larger than αGW\alpha_{GW}? A rounding achieving αGW+2−O(d)\alpha_{GW} + 2^{-O(d)} answers yes.

Result
Proved
Status
Resolved
AI contribution
AI co-developed
Method
Argument
Field
Approximation algorithms
Posed by
Adi Avidor & Uri Zwick
Year posed
2005
Years open
21y
Solved
2026-04-16
Model
Gemini (internal), ChatGPT-5.2 Extended Pro, Gemini 3.0 Pro DeepThink
Vendor
Google DeepMind / OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Preprint
Significance
10 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What the AI did

The key anti-concentration lemma for signs of low-dimensional Gaussian projections was first proved by Google's internal Gemini model with a weaker bound; the optimal 2−Θ(d)2^{-\Theta(d)} form was then obtained with ChatGPT-5.2 Extended Pro and Gemini 3.0 Pro DeepThink, with proofs edited by the authors.

Verification

Author-edited and checked arXiv preprint. Not yet peer-reviewed.

Source

arXiv:2604.13971 - Max Cut with small-dimensional SDP solutions

Discussion