Rank-sensitive vertex bounds for semidefinite lifts
We study how the ranks of factors in a positive semidefinite slack factorization constrain its size. We bound the number of low-rank vertex factors in any fixed factorization, and use this to determine the asymptotic order of the minimum factorization size under any fixed bound on vertex-factor ranks: $Θ(n\log n)$ for permutahedra $Π_n$ and $Θ(\log N)$ for regular $N$-gons. In the rank-one case this gives the order of the minimum dimension of a space of real functions on the vertices in which every facet slack is a sum of squares, with no symmetry or degree restriction. For unrestricted…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.04498
curl -X POST /api/v1/records/arxiv/2610.04498/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04498/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'