{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}