Full-Text PDF (658 KB) | Introduction as PDF | Metadata | Table of Contents | OWR summary
Published online: 2018-07-04
Proof Complexity and BeyondAlbert Atserias, Jakob Nordström, Toniann Pitassi and Alexander A. Razborov (1) Universitat Politècnica de Catalunya, Barcelona, Spain
(2) KTH - Royal Institute of Technology, Stockholm, Sweden
(3) University of Toronto, Canada
(4) University of Chicago, USA
Proof complexity is a multi-disciplinary intellectual endeavor that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focused on recent advances in our understanding of logic-based proof systems and on connections to algorithms, geometry and combinatorics research, such as the analysis of approximation algorithms, or the size of linear or semidefinite programming formulations of combinatorial optimization problems, to name just two important examples.
No keywords available for this article.
Atserias Albert, Nordström Jakob, Pitassi Toniann, Razborov Alexander: Proof Complexity and Beyond. Oberwolfach Rep. 14 (2017), 2299-2361. doi: 10.4171/OWR/2017/37