AI Proof WatchKeep up with AI contributions

Threshold for fitting a centered ellipsoid to Gaussian points

Given n independent standard Gaussian vectors xᵢ∈Rᵈ, is there a positive semidefinite matrix S satisfying xᵢᵀSxᵢ=d for every i? The predicted high-probability fitting threshold is n/d²=1/4, with separate below- and above-threshold regimes.

Why it matters and what counts as progress

Why it matters: A sharp threshold identifies when Gaussian quadratic constraints admit a common positive semidefinite fitting form.

What counts as progress: Prove existence when limsup n/d²<1/4 and nonexistence when liminf n/d²>1/4, or analyze the critical window.

How the problem developed

  1. 2013 · Conjecture [1]

    James Saunderson, Pablo A. Parrilo and Alan S. Willsky Conjectured a sharp fitting transition near n=d²/4 for independent Gaussian points, based on numerical evidence.

  2. 12 Jul 2023 · Partial result [2]

    Aaron Potechin, Paxton Turner, Prayaag Venkat and Alexander Wein Constructed fitting ellipsoids for about d²/polylog(d) Gaussian points, approaching but not reaching the conjectured scale.

  3. 10 Aug 2026 · Reported claim [3]

    Theodor Misiakiewicz and Garrett G. Wen Proved the sharp Gaussian threshold at n/d²=1/4, with bounded positive eigenvalues below threshold and no spectral restriction on the infeasibility result above it.

AI contribution

Sources

  1. Saunderson, Parrilo and Willsky, Diagonal and low-rank decompositions and fitting ellipsoids to random points
  2. Potechin, Turner, Venkat and Wein, Near-optimal fitting of ellipsoids to random points
  3. Misiakiewicz and Wen, The sharp SAT/UNSAT phase transition in random ellipsoid fitting
  4. The sharp SAT/UNSAT phase transition in random ellipsoid fitting
  5. Pith AI review of the ellipsoid-fitting proof
Website timeline

Publication dates and editorial changes.