default search action
15th CCC 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
- 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, Cliff 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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-17 20:47 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: