Proof Complexity and Beyond

  • Albert Atserias

    Universitat Politècnica de Catalunya, Barcelona, Spain
  • Jakob Nordström

    KTH - Royal Institute of Technology, Stockholm, Sweden
  • Toniann Pitassi

    University of Toronto, Canada
  • Alexander A. Razborov

    University of Chicago, USA

Abstract

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.

Cite this article

Albert Atserias, Jakob Nordström, Toniann Pitassi, Alexander A. Razborov, Proof Complexity and Beyond. Oberwolfach Rep. 14 (2017), no. 3, pp. 2299–2361

DOI 10.4171/OWR/2017/37