Fine Design Seminar Series

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.