Mathematics Colloquium: Sizes of Propositional Proofs

2008-02-22

4:10 pm; Neill 5W

Nathan Segerlind

Abstract: Propositional proof complexity studies the sizes of propositional proofs, and more generally, the computational resources needed to certify tautologies. The area has rich connections with computational complexity, algorithms, and constructive theories of arithmetic. We will elaborate on these connections, and then discuss two areas of contribution by the speaker: First, tools for analyzing the logical resources needed to prove random CNFs unsatisfiable, and to formalize approximate counting arguments, then, an analysis of the limitations of approximation algorithms based on semi-definite relaxation. The latter analysis is based upon the Lovasz-Schrijver "proof system" for zero-one programming. The talk is oriented towards non-specialists. (Dr. Segerlind is a candidate for the faculty position in Discrete Mathematics at WSU)