15. CoCo 2000: Florence, Italy
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000. IEEE Computer Society 2000 ISBN 0-7695-0674-7
Session 1
- 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
- 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
Session 7
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team