CPC Workshop Agenda

AGENDA

**Changes have been made to the Agenda. 2 titles (Razborov & Alekhnovich) have been added/changed and this has not been reflected on the copies on the registration table.> >Please make the changes right to your copy.**

Workshop on Complexity of Proofs and Computations

December 10 - December 16, 2000

Organizers:

Pavel Pudlak - IAS/Academy of Sciences of the Czech Republic

Alexander Razborov - Institute for Advanced Study

Avi Wigderson - Institute for Advanced Study

_______________________________________________________

The Workshop will be held in the Math Seminar Room in Simonyi Hall.

The Registration Desk will be open on Sunday, 12/10/00 at 8:45 am.

_______________________________________________________

SUNDAY, DECEMBER 10

9:20 -- 9:30 Welcome and Greeting

9:30 -- 10:15 Ran Raz (IAS), Regular Resolution Lower Bounds for the Weak Pigeonhole Principle

10:30 -- 11:15 Neil Thapen (Oxford University), The Weak Pigeonhole

11:30 -- 12:15 Stefan Dantchev (BRICS), "Planar" Tautologies Hard for Resolution

12:30 -- 2:15 Lunch (on your own)

2:30 -- 3:15 Michael Alekhnovich (IAS), Resolution is not automatizable unless MMSA can be efficiently approximated for small weights

3:30 -- 4:15 Eli Ben-Sasson (IAS), Linear Lower Bounds for Space of Refuting Random CNF's

4:30 -- 5:15 Nicola Galesi (IAS), Monotone Simulations of Nonmonotone Proofs