Oberwolfach Reports


Full-Text PDF (658 KB) | Introduction as PDF | Metadata | Table of Contents | OWR summary
Volume 14, Issue 3, 2017, pp. 2299–2361
DOI: 10.4171/OWR/2017/37

Published online: 2018-07-04

Proof Complexity and Beyond

Albert Atserias[1], Jakob Nordström[2], Toniann Pitassi[3] and Alexander A. Razborov[4]

(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