Institute for Advanced Study

School of Mathematics

Princeton, New Jersey

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

Abstract

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

Proofs Abstract, Slides, Paper

------------------------------------------------------------------------

MONDAY, DECEMBER 11

9:30 -- 10:15 Eric Allender (Rutgers University), Improved Uniformity

Results on Division Abstract

10:30 -- 11:15 Alan Woods (University of Western Australia), Lower Bounds

on Prime Testing - an Alternative Approach Abstract, Paper

11:30 -- 12:15 Amir Shpilka (Hebrew University), Lower Bounds for Matrix

Product, in Bounded Depth Circuits with Arbitrary Gates Abstract, Paper

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:15 -- 3:00 Gaisi Takeuti (University of Pennsylvania), A Combinatorial

Problem Related to P=NP Problem

3:00 -- 3:30 Coffee Break (Fuld Hall Common Room)

3:30 -- 4:15 Alan Skelley (University of Toronto), Relating the PSPACE Reading

Power of Boolean Programs and Quantified Boolean Formulas

4:30 -- 5:15 Dieter van Melkebeek (IAS), Time-space Tradeoffs for Satisfiability

Abstract, Paper

-----------------------------------------------------------------------

TUESDAY, DECEMBER 12

9:30 -- 10:15 Soren Riis (BRICS), Complexity Gaps in Propositional Logic

10:30 -- 11:15 Josh Buresh-Oppenheim (University of Toronto),

Homogenization and the Polynomial Calculus Abstract, Slides

11:30 -- 12:15 Michael Soltys (University of Toronto), The Complexity of

Derivations of Matrix Identities

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:15 -- 3:00 Alasdair Urquhart (University of Toronto), On the Complexity

of Analytic Tableaux Abstract, Paper

3:00 -- 3:30 Coffee Break (Fuld Hall Common Room)

3:30 -- 4:15 Jan Krajicek (Mathematical Institute of Czech Academy of

Sciences), AC^0 Functions Free For a Proof System Abstract,

4:30 -- 5:15 Tsuyoshi Morioka (University of Toronto), Type-2

Characterization of Search Problems and the Definable Functions of Bounded

Arithmetic Theories Abstract, Slides

------------------------------------------------------------------------

WEDNESDAY, DECEMBER 13

9:30 -- 10:15 Lance Fortnow (NEC Research), Comparing Notions of Full

Derandomization Abstract, Paper, Slides

10:30 -- 11:15 Valentin Kabanets (IAS), On the Complexity of Exponential

Time Abstract, Slides

11:30 -- 12:15 Venkatesh Srinivasan (IAS), The Communication Complexity

of Pointer Chasing Abstract

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:15 -- 3:00 Antonina Kolokolova (University of Toronto), A Second-Order

System for Polynomial-Time Reasoning Based on Gradel's Characterization of P Abstract, Paper, Slides

3:00 -- 3:30 Coffee Break (Fuld Hall Common Room)

3:30 -- 4:15 Arnold Beckmann (University of Munster), Ordinal Notations

and Well-Orderings in Bounded Arithmetic

4:30 -- 5:15 Maria Bonet (Lenguajes y Sistemas Informaticos), Lower bounds

and separations for extensions of resolution Paper 1, Paper 2, Slides

6:00 -- Workshop dinner (Dilworth Room) (Reservation required by 12/5/00)

--------------------------------------------------------------------------

THURSDAY, DECEMBER 14

9:30 -- 10:15 Alexander Razborov (IAS), Lower Bounds for Polynomial Calculus:

Non-Binomial Case Abstract, Slides, Paper

10:30 -- 12:30 Informal discussions

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:00 -- Informal discussions

--------------------------------------------------------------------------

FRIDAY, DECEMBER 15

-- 12:30 Informal discussions

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:00 -- Informal discussions

---------------------------------------------------------------------------

SATURDAY, DECEMBER 16

-- 12:30 Informal discussions

12:30 -- 2:00 Lunch (IAS Dining Hall)

2:00 -- 5:00 Informal discussions

5:00 -- 5:10 Closing