Id: arxiv/2608.10184 Url: https://arxiv.org/abs/2608.10184 Tags: math.PR, cond-mat.dis-nn, cs.DS, math.ST, stat.ML Score: 0 Title: The sharp SAT/UNSAT phase transition in random ellipsoid fitting Domain: math.PR Source: arxiv Authors: Theodor Misiakiewicz, Garrett G. Wen Reviews: 0 Subject: math.PR Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-10 Page: https://delphi.science/r/arxiv/2608.10184 Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = α^* 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof…