COMPUTATIONAL COMPLEXITY

Thirteenth Annual IEEE Conference

 

Sponsored by the

 

IEEE Computer Society Technical Committee on
Mathematical Foundations of Computing,

and the

University at Buffalo

 

In cooperation with

ACM-SIGACT and EATCS

 

June 15 --- 18, 1998

 

Buffalo, NY, USA

 

 

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.