No small SDP for matching?

0:00Lifts of the matching polytope

The perfect matching polytope is the convex hull of all perfect matchings of the complete graph on n vertices. Edmonds described it with simple inequalities: every edge weight nonnegative, every vertex covered exactly once, and, for every odd set of vertices, at least one unit of weight leaving it. There are exponentially many odd-set inequalities. A lift is a higher-dimensional object that projects down onto the polytope, and the question is how small such a lift can be. In 2014, Rothvoss proved that every linear lift, a polyhedron projecting onto the polytope, needs exponential size. But semidefinite lifts, slices of the cone of positive semidefinite matrices, can be far smaller than linear ones, and whether perfect matching has a polynomial-size semidefinite lift remained open. By the theory of Gouveia, Parrilo and Thomas, the smallest semidefinite lift has the size of the positive semidefinite rank of a slack matrix: one row per inequality, one column per perfect matching, entries the slack. For an odd set, the slack is the number of matching edges crossing it, minus one. The PSD rank is the smallest r such that every entry is the trace of a product of two r by r positive semidefinite matrices, one for the row and one for the column. Ordinary rank is no help: in our check, with 10 vertices, 512 odd sets and 945 matchings, the matrix has rank 36, and in general its rank is at most quadratic in n. Lee, Raghavendra and Steurer turned sum-of-squares lower bounds into general semidefinite lower bounds, Braun and Pokutta proved that a shifted version of this matrix has exponential nonnegative rank, and Braun, Pokutta and six coauthors ruled out small symmetric semidefinite lifts.

1:53The claim

Result 126 is one OpenAI preprint, 24 pages, dated October 5. Fix ρ strictly between zero and one, and add ρ to every odd-set entry. The paper claims that this shifted matrix has real PSD rank at least 2^(cn), for one absolute constant c, once n is large enough, with how large depending on ρ, with factors allowed to be any real positive semidefinite matrices, and no symmetry assumed. At ρ = 1, the entries are just crossing counts, and diagonal matrices indexed by edges factor it with size C(n, 2), so the shift must stay below one. As a corollary, every exact semidefinite lift of the perfect matching polytope has exponential size. Exactness matters: Kaniewski, Lee and de Wolf built matrices of subexponential PSD rank that approximate the unshifted slack matrix up to a tiny entrywise error. OpenAI published a Lean formalization of a weaker version that still rules out polynomial-size lifts: for every fixed power C, the PSD rank of the perfect matching slack matrix, and the size of every exact affine semidefinite lift, exceed n^C for all large even n. That is superpolynomial rather than exponential, and it is stated for the unshifted slack matrix, edge rows included, not for the shifted ones. It runs to 66 files and about 7,500 lines with its imports, not counting Mathlib, and its proof takes a different route from the argument we sketch next.

3:32How the proof goes

The obstruction is a parity puzzle on an expander graph. Each vertex carries one bit per incident edge, with a prescribed parity, and the parities add up to odd. Then some edge must see unequal bits at its two ends. Subtract 1 − ρ from the number of disagreements, and you get a positive function. Yet a linear functional, in the style of Grigoriev’s for Tseitin contradictions, is nonnegative on squares of functions whose Fourier characters touch only a small fraction of the vertices, while it treats every edge as agreeing, and so gives that positive function a negative value. In our check, degree-4 sum-of-squares moments on the Petersen graph saw zero disagreements, although every real assignment has at least one; on K4 and K3,3, degree 6 caught the contradiction. To bring this into matching, each vertex of the expander becomes a cell of k vertices, with k a large constant. Each incident edge uses one terminal, and the remaining vertices are paired inside the cell. Restrict cuts so that the terminal bits are fixed and each internal pair agrees: then the only matching edges crossing the cut are the disagreements of the parity puzzle. So averaging a row factor of a small PSD factorization over such cuts, and pairing it with a matching’s factor, reproduces the positive function exactly. The hard part is to show that a small factorization would make that function close to a sum of squares of low degree. Square roots of the row factors have no degree bound, and averaging squares is not squaring averages. So the proof builds an exact representation of the averaged factor as a sum of products, HᵀH, over branches, each labelled by a Fourier character, and pushes their coefficients toward characters that differ from the label in only a few vertex blocks. A local averaging estimate within a cell gives a variance that shrinks as k grows, with no dependence on matrix dimension, using a trace bound and lower bounds on the dimensions of invariant eigenspaces, the same spectral trick used in work on quasirandom groups. A dimension-free splitting inequality for positive semidefinite matrices, and a product averaging theorem with weights growing exponentially in the number of differing blocks, control the Fourier mass. After truncation, multiplying by the branch’s character moves each retained term to low block degree while preserving squares. The separating functional is then nonnegative on the approximation, but negative on the function it approximates. That contradiction forces the factorization to have exponential size.

6:20Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers superpolynomial lower bounds for the unshifted slack matrix and for exact affine lifts, not the exponential bound or the shifted matrices, and its proof follows a different route from the paper’s; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, perfect matching has no small exact semidefinite description: like linear lifts, semidefinite lifts need exponential size, even though a maximum-weight perfect matching can be found in polynomial time. The claim is about exact lifts and exact factorizations; matrices that only approximate the slack matrix entrywise can have far smaller PSD rank.