Sum of Squares: An Optimal Algorithm? (ft. Boaz Barak)

Sum of Squares is a candidate to be an optimal algorithm, i.e. able to efficiently solve a large portion of tractable problem, and to efficiently inform us about the hardness of hard problems. The video features Boaz Barak, Professor at Harvard, who recently visited EPFL.
boazbarak.org/
sumofsquares.org/

[@zjz19900621]

The optimality condition of SOS requires the archimedean property. It is a relaxation of convexity but still a non-trivial requirement nonetheless. Unfortunately, the problem I am currently working on does not have such a blessing.

[@keithypts]

A very approachable material to understand a little bit of this is contained in these slides by expert Pablo Parrillo: www.mit.edu/~parrilo/cdc03_workshop/08_sum_of_squares_2003_12_07_07_screen.pdf
I must say that I watched the video before and after reading the material(the first time I didn't understand almost anything) and I was surprised for the fact that is not that difficult after all.

[@tuongnguyen9391]

Oh man the link is dead can you give me again

[@syvisaur7735]

Mais D. Steurer c'est mon prof ! :0

[@syvisaur7735]

Algorithmique et structure de données ^^
Par exemple, on a étudié l'algorithme de Gale-Shapley dont Le a parlé dans sa série sur la démocratie, et sur les bases de la théorie des graphes. Après on a changé de prof ^^