Skip to main content
  • Conference proceedings
  • © 2000

STACS 2000

17th Annual Symposium on Theoretical Aspects of Computer Science Lille, France, February 17-19, 2000 Proceedings

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1770)

Conference series link(s): STACS: Annual Symposium on Theoretical Aspects of Computer Science

Conference proceedings info: STACS 2000.

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

This is a preview of subscription content, log in via an institution to check for access.

Table of contents (54 papers)

  1. Front Matter

    Pages I-XIV
  2. Codes and Graphs

    • M. Amin Shokrollahi
    Pages 1-12
  3. A Classification of Symbolic Transition Systems

    • Thomas A. Henzinger, Rupak Majumdar
    Pages 13-34
  4. On the Many Faces of Block Codes

    • Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B. Sundar Rajan
    Pages 53-64
  5. A New Algorithm for MAX-2-SAT

    • Edward A. Hirsch
    Pages 65-73
  6. Bias Invariance of Small Upper Spans

    • Jack H. Lutz, Martin J. Strauss
    Pages 74-86
  7. The Complexity of Planarity Testing

    • Eric Allender, Meena Mahajan
    Pages 87-98
  8. About Cube-Free Morphisms

    • Gwénaël Richomme, Francis Wlazinski
    Pages 99-109
  9. Two-Variable Word Equations

    • Lucian Ilie, Wojciech Plandowski
    Pages 122-132
  10. Average-Case Quantum Query Complexity

    • Andris Ambainis, Ronald de Wolf
    Pages 133-144
  11. The Boolean Hierarchy of NP-Partitions

    • Sven Kosub, Klaus W. Wagner
    Pages 157-168
  12. Binary Exponential Backoff Is Stable for High Arrival Rates

    • Hesham Al-Ammal, Leslie Ann Goldberg, Phil MacKenzie
    Pages 169-180
  13. The Data Broadcast Problem with Preemption

    • Nicolas Schabanel
    Pages 181-192
  14. An Approximate L p-Difference Algorithm for Massive Data Streams

    • Jessica H. Fong, Martin J. Strauss
    Pages 193-204
  15. Logics Capturing Local Properties

    • Leonid Libkin
    Pages 217-229
  16. The Complexity of Poor Man’s Logic

    • Edith Hemaspaandra
    Pages 230-241

Other Volumes

  1. STACS 2000

Editors and Affiliations

  • Faculty of Computer Science, Dept. of Theoretical Computer Science, Universität Dresden, Dresden, Germany

    Horst Reichel

  • Université de Lille, LIFL - UPRESA 8022, CNRS, Bât. M3 - UFR IEEA, Villeneuve d’ASCQ Cedex, France

    Sophie Tison

Bibliographic Information

Buy it now

Buying options

eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access