15. CoCo 2000: Florence, Italy

Session 1

• Lance Fortnow, Dieter van Melkebeek:
  Time-Space Tradeoffs for Nondeterministic Computation. 2-13
  
• Ketan Mulmuley, Pradyut Shah:
  A Lower Bound for the Shortest Path Problem. 14-21
  
• Iannis Tourlakis:
  Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines. 22-
  

Session 2

• Oliver Giel:
  BP(L(f)^1+epsilon). 36-43
  
• Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet:
  The Communication Complexity of Enumeration, Elimination, and Selection. 44-53
  
• Richard Cleve:
  The Query Complexity of Order-Finding. 54-
  

Session 3

• David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie:
  On the Complexity of Some Problems on Groups Input as Multiplication Tables. 62-69
  
• Carsten Damm, Markus Holzer, Pierre McKenzie:
  The Complexity of Tensor Calculus. 70-86
  
• Thanh Minh Hoang, Thomas Thierauf:
  The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. 87-
  

Session 4

• Jeff Kahn, Michael E. Saks, Clifford D. Smyth:
  A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. 98-103
  
• Gabriel Istrate:
  Computational Complexity and Phase Transitions. 104-115
  
• Oliver Kullmann:
  An Application of Matroid Theory to the SAT Problem. 116-
  

Session 5

• Harry Buhrman, Sophie Laplante, Peter Bro Miltersen:
  New Bounds for the Language Compression Problem. 126-130
  
• Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
  Combinatorial Interpretation of Kolmogorov Complexity. 131-137
  
• Nikolai K. Vereshchagin, Michael V. Vyugin:
  Independent Minimum Length Programs to Translate between Given Strings. 138-
  

Tutorial 1

• Luca Trevisan:
  A Survey of Optimal PCP Characterizations of NP. 146-
  

Session 6

• Valentine Kabanets:
  Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. 150-157
  
• Jack H. Lutz:
  Dimension in Complexity Classes. 158-169
  
• Andreas Jakoby, Rüdiger Reischuk:
  Average Case Complexity of Unbounded Fanin Circuits. 170-
  

Session 7

• Venkatesan Guruswami, Sanjeev Khanna:
  On the Hardness of 4-Coloring a 3-Colorable Graph. 188-197
  
• Marcus Schaefer:
  Deciding the K-Dimension is PSPACE-Complete. 198-203
  
• Ke Yang:
  Integer Circuit Evaluation is PSPACE-Complete. 204-
  

Session 8

• Pavol Duris, Juraj Hromkovic, Katsushi Inoue:
  A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition. 214-228
  
• George Karakostas, Richard J. Lipton, Anastasios Viglas:
  On the Complexity of Intersecting Finite State Automata. 229-234
  
• Andrei A. Voronenko:
  On the Complexity of the Monotonicity Verification. 235-238
  

Session 9

• André Berthiaume, Wim van Dam, Sophie Laplante:
  Quantum Kolmogorov Complexity. 240-249
  
• Frederic Green, Steven Homer, Chris Pollett:
  On the Complexity of Quantum ACC. 250-262
  
• Paul M. B. Vitányi:
  Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State. 263-270
  
• Ronald de Wolf:
  Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. 271-278
  

Last update Sat May 25 02:32:56 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page