Title	Size-Degree Trade-Off for Sums-of-Squares Proofs
Creator	Hakoniemi, Tuomas
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2020-01-20T16:30
Description	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.
Extent	26.0 minutes
Subject	Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: Universitat Politècnica de Catalunya
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2020-09-18
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0394417
URI	http://hdl.handle.net/2429/76074
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Graduate
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos