BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Size-Degree Trade-Off for Sums-of-Squares Proofs Hakoniemi, Tuomas


We present a size-degree trade-off for Sums-of-Squares proofs that is analogous to the previous size-width and size-degree trade-offs for resolution and polynomial calculus. We discuss a strong duality theorem between provable lower bounds and pseudoexpectation values that is key to our proof method, and ways to extend the result to Positivstellensatz proof system. Joint work with Albert Atserias.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International