Browse › Theoretical computer science › 126 Exponential semidefinite complexity of perfect matching
Exponential PSD rank of positively shifted matching matrices
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every fixed $0\lt \rho\lt 1$, the matrix indexed by odd vertex sets U and perfect matchings M of Kn, with entries $|M\cap\delta(U)|-1+\rho$, has real positive semidefinite rank $2^{\Omega(n)}$ as even n tends to infinity. Here $\delta(U)$ is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope note for family 126: Exponential semidefinite complexity of perfect matching (lean/docs/126.md, October 2026). The release's own scope note: the formalized comparator statements give superpolynomial bounds (PSD rank of the selected unshifted perfect-matching slack matrix, and the size of exact affine semidefinite lifts, exceed $n^C$ for every fixed $C>0$), not the paper's exponential bound for every fixed shift $0<\rho<1$. [AI-generated per source] [family-level]
- OpenAI math release, ComparatorChallenges/MatchingAffineLift.lean (openai/math, commit adc7f12). The comparator statement
affine_lift_lower_boundsays that for every $C>0$ an affine PSD lift of size $r$ of the perfect matching polytope has $n^C<r$ for large even $n$; this file only states the result, with the proof left assorryand developed separately in MatchingPSD. [AI-generated per source]
Related prior literature mentioned by others
- Gábor Braun et al., The matching problem has no small symmetric SDP (arXiv:1504.00703, 2 April 2015; revised 30 November 2016). Cited as the source of the compact-SDP question; it proves an exponential lower bound under symmetry assumptions, whereas the release manuscript claims a bound for arbitrary real PSD factors.
Possibly relevant literature (found by the agent, not checked)
- J. Briët, D. Dadush, S. Pokutta, On the existence of 0/1 polytopes with high semidefinite extension complexity (arXiv:1305.3268, 2013). Proves non-constructively that 0/1 polytopes with semidefinite extension complexity $2^{\Omega(n)}$ exist; context for Corollary 1.2, which claims such a bound for the explicit perfect matching polytope.
- H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, R. R. Thomas, Positive semidefinite rank (arXiv:1407.4095; Math. Program. 153 (2015)). A survey of PSD rank, the quantity bounded in Theorem 1.1, and of its relation to semidefinite representations of polytopes.
- G. Schoenebeck, Linear Level Lasserre Lower Bounds for Certain k-CSPs (FOCS 2008). Linear-level Lasserre/SoS lower bounds for XOR-type systems, related to the Grigoriev-type parity functional on expanding graphs built in the paper's parity section.
- P. Austrin, K. Risse, Perfect Matching in Random Graphs is as Hard as Tseitin (arXiv:2201.10835; TheoretiCS 1 (2022)). Reduces Tseitin formulas to perfect-matching formulas to prove Sum-of-Squares degree lower bounds; the paper's proof also realizes an expander parity system inside perfect matchings.
Digests and expositions
- Open Mathematics Courses, Semidefinite lifts of the perfect matching polytope (online course, undated). Seven lessons explain the manuscript's PSD factorizations, cell averaging, orthogonal splitting, Fourier smoothing and parity obstruction, with proofs and exercises; the site credits Claude Opus 5.5 and states that independent review is incomplete. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 126
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026,
author = {{OpenAI}},
title = {{Exponential PSD rank of positively shifted matching matrices}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026/shifted-matching-psd.pdf}{OAI:Exponential-PSD-rank-of-positively-shifted-matching-matrices-October-5-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/126.md. The Lean statements have not been checked by people against the paper's claims.
Family 126: Exponential semidefinite complexity of perfect matching
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\lt \rho\lt 1$, allowing arbitrary real positive semidefinite factors.
This is the only paper in this family.