Proof Complexity and Beyond

Abstract

Proof complexity is a multi-disciplinary research area that addresses questions of the general form “how difficult is it to prove certain mathematical facts?” The current workshop focussed on recent advances in our understanding that the analysis of an appropriately tailored concept of “proof” underlies many of the arguments in algorithms, geometry or combinatorics research that make the core of modern theoretical computer science. These include the analysis of practical Boolean satisfiability (SAT) solving algorithms, the size of linear or semidefinite programming formulations of combinatorial optimization problems, the complexity of solving total NP search problems by local methods, and the complexity of describing winning strategies in two-player round-based games, to name just a few important examples.