PROGRAM
All sessions will be in the Center for Tomorrow.
RECEPTION/REGISTRATION: Sunday from 4pm to
9pm,
and
Monday, Center For Tomorrow.
8:50--9:00
Welcoming Remarks
SESSION 1: Monday, June 15, Morning
Chair: R. Beigel (Lehigh Univ.)
9:00--9:30
On Membership Comparable Sets,
D. Sivakumar (Univ. Houston)
9:30--10:00
Nonrelativizing Separations,
H. Buhrman (CWI),
L. Fortnow (Univ. Chicago),
T. Thierauf (Univ. Ulm)
10:00--10:30
Two Queries,
H. Buhrman (CWI),
L. Fortnow (Univ. Chicago)
10:30--11:00
Break
Survey Talk 1:
Chair: J. Feigenbaum (AT&T Labs)
11:00--12:15
The Status of P vs. NP and Lower Bounds,
S. Rudich (Carnegie Mellon Univ.)
SESSION 2: Monday, June 15, Afternoon
Chair: S. Rudich (Carnegie Mellon Univ.)
2:00--2:30
Computational Indistinguishability: A Sample Hierarchy,
O. Goldreich (Weizmann Inst. and Mass. Inst. of Tech.),
M. Sudan (Mass. Inst. of Tech.)
2:30--3:00
Proofs of Membership vs. Proofs of Knowledge,
G. Di Crescenzo and R. Impagliazzo (UC San Diego)
3:00--3:30
Approximating the SVP to within a factor
(1 + 1/(dim^{epsilon})) is NP-hard under randomized reductions,
J.-Y. Cai and A. Nerurkar (Univ. at Buffalo)
3:30--4:00 Break
SESSION 3: Monday, June 15, Late Afternoon
Chair: M. Naor (Weizmann Inst.)
4:00--4:30
Arthur-Merlin Games in Boolean Decision Trees,
R. Raz (Weizmann Inst.),
G. Tardos (Math. Inst. of the Hungarian Acad. of Sci.),
O. Verbitsky (Lviv Univ.),
N. Vereshchagin (Moscow State Univ.)
4:30--5:00
On Arithmetic Branching Programs,
A. Beimel (Harvard Univ.),
A. Gal (UT Austin)
5:00--5:30
The Satisfiability Problem for Probabilistic Ordered Branching
Programs,
M. Agrawal (IIT Kanpur),
T. Thierauf (Univ. Ulm)
SESSION 4: Tuesday, June 16, Morning
Chair: D. Spielman (Mass. Inst. of Tech.)
9:00--9:30
Isolation, Matching, and Counting,
E. Allender (Rutgers Univ.),
K. Reinhardt (Univ. Tübingen)
9:30--10:00
A Note on the Hardness of Tree Isomorphism,
B. Jenner (Univ. T\"ubingen and Univ. Ulm),
P. McKenzie (Montréal Univ. and Univ. Tübingen),
J. Torán (Univ. Ulm)
10:00--10:30
Theory of Periodically Specified Problems: Complexity and
Approximability,
M. Marathe (Los Alamos Natl. Lab.),
H. Hunt, D. Rosenkrantz, R. Stearns (Univ. at Albany)
10:30--11:00
Break
Survey Talk 2:
Chair: J. Feigenbaum (AT&T Labs)
11:00--12:15
Formal Models of Computation in Complexity and Coding Theory,
D. Spielman (Mass. Inst. of Tech.)
TUESDAY AFTERNOON: Excursion to Niagara Falls.
Departure at 2pm.
SESSION 5: Wednesday, June 17, Morning
Chair: S. Fenner (Univ. Southern Maine)
9:00--9:30
How to Encode a Logical Structure as an OBDD,
H. Veith (Tech. Univ. Wien)
9:30--10:00
Complete Problems for Promise Classes by Optimal Proof Systems for
Test Sets,
J. Köbler and J. Messner (Univ. Ulm)
10:00--10:30
Lower Bounds for Computation with Limited Nondeterminism,
H. Klauck (Univ. Frankfurt)
10:30--11:00
Break
Survey Talk 3:
Chair: J. Feigenbaum (AT&T Labs)
11:00--12:15
DNA Computing,
R. Beigel and B. Fu (Lehigh Univ.)
SESSION 6: Wednesday, June 17, Afternoon
Chair: E. Mayordomo (Univ. Zaragoza)
2:00--2:30
Hard Sets are Hard to Find,
H. Buhrman (CWI),
D. van Melkebeek (CWI and Univ. Chicago)
2:30--3:00
On the Resource Bounded Measure of P/poly,
J. Köbler and W. Lindner (Univ. Ulm)
3:00--3:30
Probabilistic Martingales and BPTIME Classes,
K. Regan (Univ. at Buffalo),
D. Sivakumar (Univ. Houston)
3:30--4:00
Break
SESSION 7: Wednesday, June 17, Late Afternoon
Chair: J. Goldsmith (Univ. Kentucky)
4:00--4:30
Complexity Limitations on Quantum Computation,
L. Fortnow (Univ. Chicago),
J. Rogers (DePaul Univ.)
4:30--5:00
Relationships between quantum and classical space-bounded complexity
classes,
J. Watrous (Univ. Wisconsin at Madison)
5:00--5:30
Uniformly Hard Languages,
R. Downey (Victoria Univ.),
L. Fortnow (Univ. Chicago)
BUSINESS MEETING: From 6pm in Center For
Tomorrow.
Food and refreshments will be
served.
RUMP SESSION: After the business meeting.
SESSION 8: Thursday, June 18, Morning
Chair: A. Selman (Univ. at Buffalo)
9:00--9:30
Resource-Bounded Measure,
J. Lutz (Iowa State Univ.)
9:30--10:00
Randomness is Hard,
H. Buhrman (CWI) and L. Torenvliet (Univ. Amsterdam)
10:00--10:30
Resource-Bounded Measure and Learnability,
W. Lindner and R. Schuler (Univ. Ulm),
O. Watanabe (Tokyo Inst. of Tech.)
10:30--11:00
Break
Survey Talk 4:
Chair: J. Feigenbaum (AT&T Labs)
11:00--12:15
Complexity Issues in Markov Decision Processes,
J. Goldsmith (Univ. Kentucky),
M. Mundhenk (Univ. Trier)
CLOSE.