DIMACS Workshop on Intrinsic Complexity of Computation

April 10 - 13, 2000
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

Paul Beame, University of Washington, beame@cs.washington.edu

Steven Rudich, Carnegie Mellon University, rudich+@cs.cmu.edu

Andrew Yao, Princeton University, yao@cs.princeton.edu

Workshop Program:

Monday April 10, 2000

8:15-9:20   Breakfast and Registration

9:20-9:30   Welcome and Greeting:
            Mike Saks, Rutgers University
            Chair, Special Year on Computational Intractability

9:30-10:30  Avi Wigderson, IAS & Hebrew U.
	    (Perspective on lower bounds)
            Trials and errors?

10:30-11:00 Discussion and break

11:00-12:00 Ramamohan Paturi, UCSD
            Lower bounds for depth 3 circuits

12:00-2:00  Lunch

2:00-3:00   Miklos Ajtai, IBM Alamaden
            (Perspective on lower bounds)
	    Title: TBA

3:00-3:30   Discussion and break

3:30-4:20   Peter Bro Miltersen, U. of Aarhus
            Upper and Lower Bounds for locally decodable source codes

4:20-4:30   Discussion and break

4:30-5:00   Richard Beigel
            Lower Bounds for Approximations by Low Degree Polynomials over Z_m

Tuesday April 11, 2000

8:45-9:30   Breakfast and Registration

9:30-10:30  Steven Rudich, CMU
            (Perspective on lower bounds)
	    Title: TBA

10:30-11:00 Discussion and break

11:00-12:00 Paul Beame, U. Washington
            Super-linear time-space tradeoff lower bounds for randomized computation

12:00-2:00  Lunch

2:00-3:00   Russell Impagliazzo, UCSD
            (Perspective on lower bounds)
	    When is intractability useful?

3:00-3:30   Discussion and break

3:30-4:20   Eli Ben-Sasson, Hebrew U.
            Near-optimal separation of treelike and general resolution

4:20-4:30   Discussion and break

4:40-5:00   Nathan Segerlind, UCSD
	    Polynomial simulation of Nullstelensatz refutations
	    by bounded-depth Frege systems with counting axioms

5:00-5:30   Sam Buss, UCSD
	    On the Computational Complexity of Intuitionistic Logic


Wednesday April 12, 2000
       
8:45-9:30   Breakfast and Registration

9:30-10:30  Lance Fortnow, NECI
	    Diagonalization

10:30-11:00 Discussion and break

11:00-11:30 Ingo Wegener, U. of Dortmund
            On the necessary amount of nondeterminism in certain models of
            branching programs

11:30-12:00 Martin Sauerhoff, U. of Dortmund
            On Probability-Amplification for Read-Once Branching Programs

12:00-2:00  Lunch

2:00-3:00   Andrew Yao, Princeton
            Why I'm An Optimist

3:00-3:30   Discussion and break

3:30-4:00   Rafail Ostrovsky, Telcordia
            Computational PCP: Short One-Round Proofs for NP

Thursday April 13, 2000

8:45-9:30   Breakfast and Registration

9:30-10:15  Rudiger Reischuk, U. of Luebeck
            Relationship between SAT and Dynamic Scheduling

10:15-10:45 Discussion and Break

10:45-12:00 Roundtable on open problems and research directions

12:00       Workshop End

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage