SOS and the Dreaded Bit-complexity
summary
Claims that degree-D Sum-of-Squares proofs are computable in n^{O(D)} time are misleading: semidefinite feasibility suffers big-R / little-r bit-size issues, there are feasible SDPs whose only rational witnesses are irrational or lie doubly exponentially far from the origin, and some degree-2 SOS instances require doubly exponential coefficients to certify constant additive error. Ellipsoid plus a separation oracle still works for LPs but SDP/SOS needs PSPACE-level decision procedures in general; however optimization over the Boolean hypercube or sphere admits the usual low-degree SOS algorithms.
AI-written summary · about