CMSC 39600
Topics in Theoretical Computer SciencePrerequisites: Consent of instructor.
Catalog Description: A seminar on current research in Theoretical Computer Science.
Long Description:
Autumn 2008 Geometric Complexity (Mulmuley)
Winter 2009 Propositional Proof Complexity (Razborov) (description below)
Spring 2009 Combinatorial Group Theory [tentative] (Razborov)
PROPOSITIONAL PROOF COMPLEXITY (Winter 2009)
Proofs and computations are among the most basic concepts pertinent to virtually any intellectual human activity. On the intuitive and practical level it was perceived for centuries that particular proofs or computations can perform very differently in terms of their "efficiency", "complexity" or "feasibility" understood e.g. in terms of length, time or space consumed or "inherent", "logical" complexity. And, as long as computations are concerned, rigorous formalizations of these notions developed some 40-50 years ago eventually gave rise to what we call today Theoretical Computer Science.
It is much less known that there has been a similar and largely parallel effort for proofs, and the theory of feasible proofs resulted from this effort is precisely the main theme of our course. We will pay a special attention to rich and striking connections existing between proof complexity, computational complexity and (somewhat surprisingly) cryptographic primitives. Even if we specifically emphasize in this course more combinatorial approach provided by the framework of propositional calculus (whence comes its title), we will pay a considerable attention to the logical origins of Proof Complexity (Bounded Arithmetic, witnessing theorems). And at the later stages of the course we will be dealing with deep and hard results (predominantly lower bounds and approaches to them) that define the frontier of our current knowledge. As a consequence, we expect to pinpoint many important (but presumably difficult) open problems.
Instructors: Ketan Mulmuley, Alexander RazborovQuarter offered: AUT, WIN, SPR
Last Verified by Sharon Salveter on 11 November, 2008.