13. CoCo 1998: Buffalo, New York, USA

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 Thu May 24 04:15:02 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page