Let x_1,…,x_n∈R^d be independent standard Gaussian vectors, and let n=n(d) as d→∞. The ellipsoid fitting conjecture predicts a sharp threshold at n/d^2=1/4: if limsup_d→∞n/d^2 1/4, then with probability tending to 1 there is no symmetric positive semidefinite matrix A∈R^d× d satisfying x_i^mathsf TAx_i=1 for every i.

Ellipsoid fitting conjecture

Let $x_1,\ldots,x_n\in\mathbb{R}^d$ be independent standard Gaussian vectors, and let $n=n(d)$ as $d\to\infty$ . The ellipsoid fitting conjecture predicts a sharp threshold at $n/d^2=1/4$ : if $\limsup_{d\to\infty}n/d^2<1/4$ , then with probability tending to $1$ there exists a symmetric positive definite matrix $A\in\mathbb{R}^{d\times d}$ such that $x_i^{\mathsf T}Ax_i=1$ for every $i$ ; if $\liminf_{d\to\infty}n/d^2>1/4$ , then with probability tending to $1$ there is no symmetric positive semidefinite matrix $A\in\mathbb{R}^{d\times d}$ satisfying $x_i^{\mathsf T}Ax_i=1$ for every $i$ .

References

Primary source

arXiv

Additional references

Universality and sharp thresholds for ellipsoid fitting — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

Two August 2026 papers claim to settle the conjecture for Gaussian data, but the broader version remains open.

The conjecture was posed by Saunderson, Parrilo, and Willsky in work from 2011–2013 and predicts a sharp feasibility transition for fitting an ellipsoid through random Gaussian points.

Known results

Potechin (2023): constructed fitting ellipsoids up to $n=d^2/\operatorname{polylog}(d)$ , far below the conjectured threshold.
Bandeira and Maillard (2023): established an approximate transition at $n/d^2=1/4$ under a bounded-spectrum condition.
Earlier work established only weaker satisfiability bounds and the dimension-count obstruction above $d(d+1)/2$ .

August 2026 Gaussian resolution claims

On August 12, 2026, one preprint claimed the exact Gaussian threshold: feasibility with high probability when $\limsup n/d^2<1/4$ and infeasibility when $\liminf n/d^2>1/4$ , removing the prior approximate-fitting and spectral-bound restrictions. A second preprint claimed the same threshold up to a vanishing factor. These claims are not independently verified. A separate August 2026 report describes a fourth-moment-universal extension, but the supplied evidence does not establish its full scope.

Current status (as of August 2026): The Gaussian proportional-regime case at threshold $1/4$ is claimed solved but remains unverified; the conjecture beyond that setting remains open.

Sources

No solutions have been posted yet.