2
$\begingroup$

Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ constraint? (which corresponds to working on the hypercube $\{-1,1\}^n$)


Anything which is directly formulated as a CSP will always be of this "simple" type where the only constraint is the Boolean hypercube constraint. But lets say the question is such that one can't see that being immediately writable as a CSP and hence one has non-trivial constraints.

$\endgroup$
  • $\begingroup$ What do you mean by "a SoS hardness proof"? Do you mean a SoS problem instance of that form? Then the answer is of course yes; you can just write one down. If you mean a proof of hardness of some algorithmic problem, please expand the phrase to elaborate what you mean. $\endgroup$ – D.W. Apr 1 '16 at 16:22
  • $\begingroup$ I think the OP means a degree lower bound. $\endgroup$ – Yuval Filmus Apr 1 '16 at 17:59
  • $\begingroup$ I mean showing of lower bounds on the degree of the SOS program needed to solve a certain optimization question. Like recently it has been done for Max-Clique. The cases for which we know such bounds seem to all be over just the Boolean hypercube constarints. Is there a way to do that over non-trivial constraints? Like some linear equation between the variables? $\endgroup$ – gradstudent Apr 4 '16 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.