Kilian Risse: Some new applications of Razborov's pseudo-width method
Time: Mon 2019-03-11 12.00
Lecturer: Kilian Risse
Location: Room 4523, Lindstedtsvägen 5 - floor 5
Lunch is served at 12:00 noon (register at www.csc.kth.se/tcs/seminars/lunch/2019-03-11 at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.
There will be a more detailed technical discussionafter the seminar. This is Kilian's 30% seminar.
Resolution is arguably the most well-studied proof system for certifying unsatisfiability of Boolean formulas. The size-width bound in the celebrated paper by Ben-Sasson and Wigderson shows that for resolution proofs linear lower bounds on the width, measured in the number of variables, imply exponential size lower bounds. This method does not extend
to formulas where such strong width lower bounds are simply not true --- e.g., for the so called weak pigeonhole principle formulas claiming that m pigeons can be mapped one-to-one to n holes for m >> n. In a break-through result in 2001 Raz proved exponential size lower bounds for such formulas, which Razborov subsequently strengthened and generalized with his so-called pseudo-width method developed in a series of papers. In this seminar we discuss this framework and show how to generalize it further in order to obtain size lower bounds for other formulas. This seminar is based on joint work with Susanna F. de Rezende, Jakob Nordström and Dmitry Sokolov.
For more information about upcoming seminars, visit www.kth.se/tcs/seminars-events