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 Pudl�k - 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.
Messages for workshop guests may be left by calling (609) 734-8100 and will be placed on the bulletin board in the lobby of 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
Principle and Bounded Arithmetic Paper
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 Abstract
4:30 -- 5:15 Nicola Galesi (IAS), Monotone Simulations of Nonmonotone<