Exponential semidefinite complexity of perfect matching
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
Proves that every exact semidefinite lift of the perfect matching polytope has exponential size, answering Rothvoss's polynomial-size lift question negatively. The bound holds even for the positive semidefinite rank of its odd-cut slack matrix after any fixed shift 0< \rho< 1, allowing arbitrary real positive semidefinite factors.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Exponential PSD rank of positively shifted matching matrices
For every fixed 0< \rho< 1, the matrix indexed by odd vertex sets U and perfect matchings M of K_(n), with entries |M\capδ(U)|-1+\rho, has real positive semidefinite rank 2^{\Omega(n)} as even n tends to infinity. Here δ(U) is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has…
Full source abstract
For every fixed 0< \rho< 1, the matrix indexed by odd vertex sets U and perfect matchings M of K_(n), with entries |M\capδ(U)|-1+\rho, has real positive semidefinite rank 2^{\Omega(n)} as even n tends to infinity. Here δ(U) is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.