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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International