Open Collections

Semialgebraic Proofs and Efficient Algorithm Design

Banff International Research Station for Mathematical Innovation and Discovery

Over the past several decades, an exciting interplay between proof systems and algorithms has emerged. Several prominent algorithms can be viewed as direct translations of proofs that a solution exists into an algorithm for finding that solution. Perhaps nowhere is this connection more prominent than in the context of semi-algebraic proof systems and large classes linear and semi-definite programs. The proof system perspective, in this context, has provided fundamentally new tools for both algorithm design and analysis. These news tools have helped in both designing better algorithms for well-studied problems and proving tight lower bounds on such techniques. This talk will focus on this connection for the Sum-of-Squares proof system. In the first half, I will develop Sum-of-Squares both as a proof system and as a meta-algorithm. In doing so, I will discuss issues such as the duality between these two perspectives, and under what conditions Sum-of-Squares can be assumed to be automatizable. The second half of the talk will survey the landscape of Sum-of-Squares. This will include how Sum-of-Squares relates to other proof systems and to other semi-definite programs. As well, I will survey some of the applications of the connection between these two perspectives of Sum-of-Squares to the design of efficient algorithms for a variety of optimization problems.

Mathematics; Computer science; Mathematical logic and foundations; Theoretical computer science

video/mp4

Author affiliation: University of Toronto

2020-09-18

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/76073

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/