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

Name: STACS 2000 : 17th Annual Symposium on Theortical Aspects of Computer Science, Lille, France, February 17-19, 2000, Proceedings
Rating: 0 (0 reviews)
ISBN: 9783540671411

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

By: Horst Reichel (Editor), Sophie Tison (Editor)

Be the first to write a review

Paperback Published: March 2000
ISBN: 9783540671411
Number Of Pages: 670

Paperback

$204.16

or 4 easy payments of $51.04 with

Learn more

BUY NOW

Add to Wishlist

Ships in 10 to 15 business days

Earn 408 Qantas Points
on this Book

Description
Table of Contents
Product Details

This book constitutes the refereed proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2000, held in Lille, France in February 2000.The 51 revised full papers presented together with the three invited papers were carefully reviewed and selected from a total of 146 submissions on the basis of some 700 reviewers' reports. The papers address fundamental issues from all current areas of theoretical computer science including algorithms, data structures, automata, formal languages, complexity, verification, logic, cryptography, graph theory, optimization, etc.

Codes and Graphs	p. 1
A Classification of Symbolic Transition Systems	p. 13
Circuits versus Trees in Algebraic Complexity	p. 35
On the Many Faces of Block Codes	p. 53
A New Algorithm for MAX-2-SAT	p. 65
Bias Invariance of Small Upper Spans	p. 74
The Complexity of Planarity Testing	p. 87
About Cube-Free Morphisms	p. 99
Linear Cellular Automata with Multiple State Variables	p. 110
Two-Variable Word Equations	p. 122
Average-Case Quantum Query Complexity	p. 133
Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs	p. 145
The Boolean Hierarchy of NP-Partitions	p. 157
Binary Exponential Backoff Is Stable for High Arrival Rates	p. 169
The Data Broadcast Problem with Preemption	p. 181
An Approximate L^p-Difference Algorithm for Massive Data Streams	p. 193
Succinct Representations of Model Based Belief Revision	p. 205
Logics Capturing Local Properties	p. 217
The Complexity of Poor Man's Logic	p. 230
Fast Integer Sorting in Linear Space	p. 242
On the Performance of WEAK-HEAPSORT	p. 254
On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers	p. 267
Real-Time Automata and the Kleene Algebra of Sets of Real Numbers.	p. 279
Small Progress Measures for Solving Parity Games	p. 290
Multi-linearity Self-Testing with Relative Error	p. 302
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies	p. 314
Hard Instances of Hard Problems	p. 324
Simulation and Bisimulation over One-Counter Processes	p. 334
Decidability of Reachability Problems for Classes of Two Counters Automata	p. 346
Hereditary History Preserving Bisimilarity Is Undecidable	p. 358
The Hardness of Approximating Spanner Problems	p. 370
An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality	p. 382
¿-Coloring of Graphs	p. 395
Optimal Proof Systems and Sparse Sets	p. 407
Almost Complete Sets	p. 419
Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results	p. 431
An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications	p. 443
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem	p. 455
Controlled Conspiracy-2 Search	p. 466
The Stability of Saturated Linear Dynamical Systems Is Undecidable	p. 479
Tilings: Recursivity and Regularity	p. 491
Listing All Potential Maximal Cliques of a Graph	p. 503
Distance Labeling Schemes for Well-Separated Graph Classes	p. 516
Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs	p. 529
Characterizing and Deciding MSO-Definability of Macro Tree Transductions	p. 542
Languages of Dot-Depth 3/2	p. 555
Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures	p. 567
The CNN Problem and Other fc-Server Variants	p. 581
The Weighted 2-Server Problem	p. 593
On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem	p. 605
Spectral Bounds on General Hard Core Predicates	p. 614
Randomness in Visual Cryptography	p. 626
Online Dial-a-Ride Problems: Minimizing the Completion Time	p. 639
The Power Range Assignment Problem in Radio Networks on the Plane	p. 651
Author Index	p. 661
Table of Contents provided by Publisher. All Rights Reserved.

ISBN: 9783540671411
ISBN-10: 3540671412
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 670
Published: March 2000
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6 x 3.48
Weight (kg): 0.94