Marc Vinyals: Lower Bounds (Slightly) Beyond Resolution

Lunch is served at 12:00 noon (register at doodle.com/7m5756kwv38k4i2c by Thursday Oct 10 at 8 pm). 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

One of the goals of proof complexity is to show lower bounds for stronger and stronger proof systems. For the well-known resolution proof systems exponential lower bounds are known for many formula families, but for stronger proof systems many of these formulas quickly become either provably easy or very hard to analyze.

In this talk, we will look at k-DNF resolution, an extension of resolution that works with k-DNF formulas instead of clauses, which is exponentially more powerful than resolution yet weak enough so that one can prove interesting lower bounds and see how the hardness of different formulas change. We will show exponential lower bounds for the weak pigeonhole principle and for random k-CNF formulas as well as separations between k-DNF and (k+1)-DNF resolution for increasing k. The main technical tool is a version of the switching lemma that works for restrictions that set only a small fraction of the variables and is applicable to DNF formulas with small terms.

This presentation is based on the paper Segerlind, Buss, Impagliazzo: A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution ( dx.doi.org/10.1137/S0097539703428555 ).