Using Symmetry in Semidefinite Programming
summary
Claims that certifying nonnegativity of an SN‑invariant polynomial on the k‑subset {0,1} hypercube admits sum‑of‑squares certificates whose semidefinite program size does not grow with n, only with the SOS degree d, and that the block sizes are constant in n. Uses SDP plus representation theory to pick a few partitions, constructs symmetry‑adapted spanning sets (not bases) of bounded size, and shows Razborov’s flag spanning sets match these constructions; degree dependence is polynomial in d and the certificates work for k≥2.
AI-written summary · about