2 options
Computational complexity. proceedings : Fifteenth Annual IEEE Conference on Computational Complexity : July 4-7, 2000, Florence, Italy / sponsored by the IEEE Computer Society, Technical Committee on Mathematical Foundations of Computing ; in cooperation with ACM SIGACT, EATCS.
- Format:
- Book
- Conference/Event
- Conference Name:
- IEEE Conference on Computational Complexity (15th : 2000 : Florence, Italy)
- Language:
- English
- Subjects (All):
- Computational complexity--Congresses.
- Computational complexity.
- Nonlinear boundary value problems--Congresses.
- Nonlinear boundary value problems.
- Polynomials--Congresses.
- Polynomials.
- Logic programming--Congresses.
- Logic programming.
- Genre:
- Conference papers and proceedings.
- Physical Description:
- x, 279 pages : illustrations
- Other Title:
- 15th Annual IEEE Conference on Computational Complexity
- Computational Complexity, 2000, proceedings, 15th Annual IEEE Conference on.
- Place of Publication:
- Los Alamitos, Calif. : IEEE Computer Society, [2000]
- System Details:
- Mode of access: World Wide Web.
- text file
- Contents:
- Time-Space Tradeoff Lower Bounds for Non-Uniform Computation / P. Beame
- Time-Space Tradeoffs for Nondeterministic Computation / L. Fortnow, D. van Melkebeek 2
- A Lower Bound for the Shortest Path Problem / K. Mulmuley, P. Shah 14
- Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines / I. Tourlakis 22
- BP (f) = O (L (f)[superscript 1+varepsilon]) / O. Giel 36
- The Communication Complexity of Enumeration, Elimination, and Selection / A. Ambainis, H. Buhrman, W. Gasarch, B. Kalyanasundaram, L. Torenvliet 44
- The Query Complexity of Order-Finding / R. Cleve 54
- On the Complexity of Some Problems on Groups Input as Multiplication Tables / D. Barrington, P. Kadau, K-J. Lange, P. McKenzie 62
- The Complexity of Tensor Calculus / C. Damm, M. Holzer, P. McKenzie 70
- The Complexity of Verifying the Characteristic Polynomial and Testing Similarity / T. Hoang, T. Thierauf 87
- A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture / J. Kahn, M. Saks, C. Smyth 98
- Computational Complexity and Phase Transitions / G. Istrate 104
- An Application of Matroid Theory to the SAT Problem / O. Kullmann 116
- New Bounds for the Language Compression Problem / H. Buhrman, S. Laplante, P. Miltersen 126
- Combinatorial Interpretation of Kolmogorov Complexity / A. Romashchenko, A. Shen, N. Vereshchagin 131
- Independent Minimum Length Programs to Translate between Given Strings / N. Vereschagin, M. Vyugin 138
- A Survey of Optimal PCP Characterizations of NP / L. Trevisan 146
- Easiness Assumptions and Hardness Tests: Trading Time for Zero Error / V. Kabanets 150
- Dimension in Complexity Classes / J. Lutz 158
- Average Case Complexity of Unbounded Fanin Circuits / A. Jakoby, R. Reischuk 170
- On the Hardness of 4-Coloring a 3-Colorable Graph / V. Guruswami, S. Khanna 188
- Deciding the K-Dimension is PSPACE-Complete / M. Schaefer 198
- Integer Circuit Evaluation is PSPACE-Complete / K. Yang 204
- A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition / P. Duris, J. Hromkovic, K. Inoue 214
- On the Complexity of Intersecting Finite State Automata / G. Karakostas, R. Lipton, A. Viglas 229
- On the Complexity of the Monotonicity Verification / A. Voronenko 235
- What Complexity and Cryptography Can Teach Each Other / R. Impagliazzo
- Quantum Kolmogorov Complexity / A. Berthiaume, W. van Dam, S. Laplante 240
- On the Complexity of Quantum ACC / F. Green, S. Homer, C. Pollett 250
- Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State / P. Vitanyi 263
- Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity / R. de Wolf 271.
- Notes:
- Includes bibliographical references and author index.
- "IEEE Computer Society Order Number PR00674."
- ISBN:
- 0769506747
- 9780769506746
- 0769506755
- 9780769506753
- OCLC:
- 44631603
- Access Restriction:
- Restricted for use by site license.
The Penn Libraries is committed to describing library materials using current, accurate, and responsible language. If you discover outdated or inaccurate language, please fill out this feedback form to report it and suggest alternative language.