Susanna F. de Rezende: Size-space trade-offs in proof complexity

PRACTICALITIES

• The first part of the presentation starts at 13:15 pm and ends at 14:00.
• Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

ABSTRACT

The study of proof size, proof size, and size-space trade-offs has recently been an active line of research in proof complexity. This study was originally motivated by concerns in applied SAT solving, but has also led to questions of intrinsic interest to proof complexity.

The resolution proof system underlying current state-of-the-art SAT solvers is now fairly well-understood in this regard, but for stronger proof systems many open problems remain. In this talk, we will give an overview of what is known and then present our current research aimed at obtaining size-space trade-offs for the cutting planes proof system.

[This seminar also doubles as Susanna's official 30% PhD level presentation.]