Fall 2015

Fine Design Seminar Series

Monday, November 9th, 2015, 11:00 am12:30 pm

Add to Calendar


Nicola Galesi (Sapienza University of Rome)


Calvin Lab Room 116

Space Complexity of Refuting Random k-CNFs and a Generalization of Hall's Theorem

After shortly introducing to the space complexity of proofs, I will present a recent general framework to prove optimal space lower bounds for refuting random k-CNFs in algebraic proof systems (monomial space) and Resolution (total space). The case k=3 is based on a form of Hall's theorem where instead of matchings we consider certain connected components, which might find other applications.