The paper tackles a classic geometry problem: given a large collection of random points in high-dimensional space, when can you find an ellipsoid that passes exactly through all of them? An ellipsoid is a generalization of a sphere that can be stretched and tilted in any direction. The question is whether a centered ellipsoid exists whose surface contains every point in the dataset. The authors prove that there is a sharp threshold governing this question: if the number of points n is less than roughly a quarter of the square of the dimension d, such an ellipsoid almost certainly exists; if n exceeds that threshold, it almost certainly does not. This confirms a conjecture made over a decade ago by Saunderson, Parrilo, and Willsky.
The threshold itself has a clean interpretation. Fitting an ellipsoid is equivalent to solving a certain optimization problem over the cone of positive semidefinite matrices, and the critical value n around d squared over 4 matches a quantity called the statistical dimension of that cone. This is essentially a measure of the cone's "size" in a precise probabilistic sense, and it governs when random constraints transition from being collectively satisfiable to collectively impossible to satisfy. The sharpness of the transition, meaning it happens abruptly rather than gradually, is a hallmark of many random geometry and statistical physics problems.
The proof is technically demanding on both sides of the threshold. To show an ellipsoid exists when n is below the threshold, the authors construct a solution by splitting the problem into a small "head" involving the most challenging constraints and a smoother "tail" handled using Gaussian approximation tools. To show no ellipsoid exists above the threshold, they decompose any candidate matrix into a low-rank part and a diffuse remainder, then apply a probabilistic argument from convex geometry called a Gordon escape theorem. Together, these techniques close gaps left open in earlier related work and establish the full sharp phase transition rigorously.