The Ellipsoid Fitting Conjecture
Given n independent standard Gaussian vectors in R^d, an ellipsoid fit is a positive semidefinite S with x_i' S x_i = d for every i. Saunderson, Parrilo and Willsky conjectured that this semidefinite feasibility problem has a sharp threshold at n ~ d^2/4. Proved: below the threshold a fit exists with probability tending to one, above it none does.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Random matrix theory
- Posed by
- James Saunderson, Pablo A. Parrilo, Alan S. Willsky
- Year posed
- 2013
- Years open
- 13y
- Solved
- 2026-08-10
- Model
- GPT-5.6
- Vendor
- OpenAI
- Collaborators
- Theodor Misiakiewicz, Garrett G. Wen
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 30 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Closes both gaps left open by Bandeira and Maillard: exact fitting, and removal of the operator-norm constraint. The threshold turns out to be governed by the statistical dimension d(d+1)/4 of the PSD cone.
What the AI did
The approach is the authors' own - they say so, and trace it to the dual formulation of Bandeira and Maillard. What the model did is named step by step: ChatGPT 5.4 and 5.5 were used "to explore several possible proof strategies", and then, "Given an earlier draft, GPT 5.6 helped repair and complete several arguments, including the tightened head-tail decomposition in Lemma 3.5 and the decomposition used in the proof of Proposition 4.4, which ultimately led to the completion of the proofs."
Verification
A preprint days old, with no independent review.
Source
- PaperarXiv