Ilario Bonacina: Space for random CNFs in proof complexity

Practicalities
Lunch is served at 12:00 noon (register at  this doodle at the latest on Monday April 6). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

Abstract

The aim of this talk is to give an overview of some recent results about space lower bounds in proof complexity. In particular, for random 3-CNFs we will present a (reasonably complete) proof of an optimal monomial space lower bound for Polynomial Calculus with Resolution (PCR) and an optimal total space lower bound in Resolution. We will see how to apply a fairly general combinatorial framework for proving space lower bounds in Resolution and PCR and, more in detail, the difficulties we had to overcame for the particular case of random 3-CNFs.

A crucial point is a result independent from proof complexity: a variation of Hall's Theorem for matchings. We show that in bipartite graphs G with bipartition (L,R) and left-degree at most 3, L can be covered by certain families of disjoint paths, called VW-matchings, provided that L expands in R by a factor of 2-ε for ε > 1/23.

This talk is mainly based on a joint work with Patrick Bennett, Nicola Galesi, Tony Huynh, Mike Molloy and Paul Wollan.