- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Size-Degree Trade-Off for Sums-of-Squares Proofs
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Size-Degree Trade-Off for Sums-of-Squares Proofs Hakoniemi, Tuomas
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.
Item Metadata
Title |
Size-Degree Trade-Off for Sums-of-Squares Proofs
|
Creator | |
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 | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Universitat Politècnica de Catalunya
|
Series | |
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 | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International