STACS 2003 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003. Proceedings
| Other Authors: | , |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2003, 2003
|
| Edition: | 1st ed. 2003 |
| Series: | Lecture Notes in Computer Science
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- Competing Provers Yield Improved Karp-Lipton Collapse Results
- One Bit of Advice
- Strong Reductions and Immunity for Exponential Time
- The Complexity of Membership Problems for Circuits over Sets of Natural Numbers
- Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem
- Cake-Cutting Is Not a Piece of Cake
- The Price of Truth: Frugality in Truthful Mechanisms
- Untameable Timed Automata!
- The Intrinsic Universality Problem of One-Dimensional Cellular Automata
- On Sand Automata
- Adaptive Sorting and the Information Theoretic Lower Bound
- A Discrete Subexponential Algorithm for Parity Games
- Cryptographically Sound and Machine-Assisted Verification of Security Protocols
- Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic
- Invited Papers
- Logic as a Query Language: From Frege to XML
- How Does Computer Science Change Molecular Biology?
- Contributed Papers
- Improved Compact Visibility Representation of Planar Graph via Schnyder’s Realizer
- Rectangle Visibility Graphs: Characterization, Construction, and Compaction
- Approximating Geometric Bottleneck Shortest Paths
- Optimization in Arrangements
- Complete Classifications for the Communication Complexity of Regular Languages
- The Commutation with Codes and Ternary Sets of Words
- On the Confluence of Linear Shallow Term Rewrite Systems
- Wadge Degrees of ?-Languages of Deterministic Turing Machines
- Faster Deterministic Broadcasting in Ad Hoc Radio Networks
- Private Computations in Networks: Topology versus Randomness
- On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements
- Lattice Reduction by Random Sampling and Birthday Methods
- On the Ultimate Complexity of Factorials
- Algebraic Characterizations of Small Classes of Boolean Functions
- On the Difficulty of Some Shortest Path Problems
- Representing Graph Metrics with Fewest Edges
- Computing Shortest Paths with Uncertainty
- Solving Order Constraints in Logarithmic Space
- The Inversion Problem for Computable Linear Operators
- Algebras of Minimal Rank over Arbitrary Fields
- Evolutionary Algorithms and the Maximum Matching Problem
- Alternative Algorithms for Counting All Matchings in Graphs
- Strong Stability in the Hospitals/Residents Problem
- The Inference Problem for Propositional Circumscription of Afine Formulas Is coNP-Complete
- Decidable Theories of Cayley-Graphs
- The Complexity of Resolution with Generalized Symmetry Rules
- Colouring Random Graphs in Expected Polynomial Time
- An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation
- Finding Large Independent Sets in Polynomial Expected Time
- Distributed Soft Path Coloring
- On the Effective Jordan Decomposability
- Fast Algorithms for Extended Regular Expression Matching and Searching
- Algorithms for Transposition Invariant String Matching (Extended Abstract)
- On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets
- Some Results on Derandomization
- On the Representation of Boolean Predicates of the Diffie-Hellman Function
- Quantum Circuits with Unbounded Fan-out
- Analysis of the Harmonic Algorithm for Three Servers
- Non-clairvoyant Scheduling for Minimizing Mean Slowdown
- Space Efficient Hash Tables with Worst Case Constant Access Time
- Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure
- Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs
- Randomness versus Nondeterminism for Read-Once and Read-k BranchingPrograms
- Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids