13. CoCo 1998: Buffalo, New York, USA

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, Buffalo, New York, USA, June 15-18, 1998. IEEE Computer Society 1998, ISBN 0-8186-8395-3

Session 1

D. Sivakumar:
On Membership Comparable Sets. 2-7
Harry Buhrman, Lance Fortnow, Thomas Thierauf:
Nonrelativizing Separations. 8-12
Harry Buhrman, Lance Fortnow:
Two Queries. 13-

Session 2

Oded Goldreich, Madhu Sudan:
Computational Indistinguishability: A Sample Hierarchy. 24-33
Giovanni Di Crescenzo, Russell Impagliazzo:
Proofs of Membership vs. Proofs of Knowledge. 34-45
Jin-yi Cai, Ajay Nerurkar:
Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions. 46-

Session 3

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolai K. Vereshchagin:
Arthur-Merlin Games in Boolean Decision Trees. 58-67
Amos Beimel, Anna Gál:
On Arithmetic Branching Programs. 68-80
Manindra Agrawal, Thomas Thierauf:
The Satisfiability Problem for Probabilistic Ordered Branching Programs. 81-

Session 4

Eric Allender, Klaus Reinhardt:
Isolation, Matching, and Counting. 92-100
Birgit Jenner, Pierre McKenzie, Jacobo Torán:
A Note on the Hardness of Tree Isomorphism. 101-105
Madhav V. Marathe, Harry B. Hunt III, Daniel J. Rosenkrantz, Richard Edwin Stearns:
Theory of Periodically Specified Problems: Complexity and Approximability. 106-

Survey Talk 2

Daniel A. Spielman:
Models of Computation in Coding Theory. 120-

Session 5

Helmut Veith:
How to Encode a Logical Structure by an OBDD. 122-131
Johannes Köbler, Jochen Messner:
Complete Problems for Promise Classes by Optimal Proof Systems for Test Sets. 132-140
Hartmut Klauck:
Lower Bounds for Computation with Limited Nondeterminism. 141-

Survey Talk 3

Richard Beigel, Bin Fu:
Solving Intractable Problems with DNA Computing. 154-

Session 6

Harry Buhrman, Dieter van Melkebeek:
Hard Sets are Hard to Find. 170-181
Johannes Köbler, Wolfgang Lindner:
On the Resource Bounded Measure of P/poly. 182-185
Kenneth W. Regan, D. Sivakumar:
Probabilistic Martingales and BPTIME Classes. 186-

Session 7

Lance Fortnow, John D. Rogers:
Complexity Limitations on Quantum Computation. 202-209
John Watrous:
Relationships Between Quantum and Classical Space-Bounded Complexity Classes. 210-227
Rodney G. Downey, Lance Fortnow:
Uniformly Hard Languages. 228-

Session 8

Jack H. Lutz:
Resource-Bounded Measure. 236-248
Harry Buhrman, Leen Torenvliet:
Randomness is Hard. 249-260
Wolfgang Lindner, Rainer Schuler, Osamu Watanabe:
Resource Bounded Measure and Learnability. 261-

Survey Talk 4

Judy Goldsmith, Martin Mundhenk:
Complexity Issues in Markov Decision Processes. 272-280

Last update Fri May 24 01:46:29 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page