Fall 2015

Fine Design Seminar Series

Nov 9, 2015 11:00 am – 12: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.