DIMACS Theory Seminar - Princeton


Some Gems of Haken


Avi Wigderson
Hebrew University
(Visiting IAS and Princeton University)


Institute for Advanced Study
Math Buillding Seminar Room
Princeton University


1:45 PM
Monday, December 4, 1995


This will be a two talk series, devoted to Haken's method of obstacles. Each of the talks will be self contained.

The first talk, on Friday Dec 1, 11:45am, Princeton Theory Lunch Seminar Computer Science Building Rm 402.

In this talk I'll describe Haken's recent proof that Clique requires exponential size monotone circuits. I will explain the similarities and disticntions from Razborov's approximation method, using which such bounds were proved 10 years ago. A nice feature of Haken's proof is that it uses no nontrivial combinatorics.

The second talk, on Monday Dec 4, 1:45 pm, Institute for Advanced Study, Math building seminar room.

In that talk I'll describe Haken's breakthrough from 1985, proving that certain propositional tautologies, like the pigeonhole principle, require exponentially long resolution proofs. Resolution is a simple complete propositional proof system, often used in automated theorem proving.

Document last modified on November 29, 1995