Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 8 down vote favorite
1

Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares. Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting? (It seems that they are some kind of dual to Lassere proof system?)

share|improve this question
4  
There is some overview in arxiv.org/abs/1211.1958 . The basic SOS system is defined in passing on page 3 (look for Grigoriev and Vorobjov). – Emil Jeřábek Nov 20 '12 at 17:50
1  
@Emil, it seems that the paper contains the answers to the questions in the post (it explains the system, its history, and its relevance to recent works), why not post your comment as an answer? – Kaveh♦ Nov 21 '12 at 5:35

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.