1 min readApr 24, 2018
Relaxing a space generally makes the dual space smaller, and often makes it much nicer. For example, suppose I want to show that a certain family of constraints on the boolean hypercube are unsatisfiable. If I want to prove this over the hypercube, it might take exponential length. If I take the Lasserre relaxation of the hypercube, and the constraints remain unsatisfiable, then I can find a short sum-of-squares proof of that fact.