STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, ProceedingsVolker Diekert, Michel Habib The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of March 25-27, 2004 at the Corum, Montpellier was the twenty-?rst in this series. Previous meetings took place in Paris (1984), Saarbruc ] ken (1985), Orsay (1986), Passau (1987), Bordeaux (1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg ] (1993), Caen(1994), Munc ] hen(1995), Grenoble(1996), Lub ] eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), and Berlin (2003). The symposium looks back at a remarkable tradition of over 20 years. The interest in STACS has been increasing continuously during recent years and has turned it into one of the most signi'cant conferences in theoretical computer science. The STACS 2004 call for papers led to more than 200 submissions from all over the world. Thereviewingprocesswasextremelyhard: morethan800reviewsweredone. We would like to thank the program committee and all external referees for the valuable work they put into the reviewing process of this conference. We had a two-day meeting for the program committee in Montpellier during November 21-22, 2003. Just 54 papers (i.e., 27% of the submissions) could be accepted, as we wanted to keep the conference in its standard format with only two parallel sessions. This strict selection guaranteed the very high scienti'c quality of the conference. |
Contents
Invited Lectures | 1 |
Structural Complexity | 19 |
Constant Width Planar Computation Characterizes ACC0 | 44 |
SumMulticoloring on Paths | 68 |
Matching Algorithms Are Fast in Sparse Random Graphs | 81 |
Quantum Identification of Boolean Oracles | 105 |
Pattern Inference and Statistics | 117 |
Satisfiability Constraint Satisfaction Problem | 141 |
Integral Symmetric 2Commodity Flows | 406 |
Logic and Formal Languages | 428 |
Active ContextFree Games | 452 |
Graphs Algorithms II | 465 |
Smoothed Competitiveness of Metrical | 489 |
The Plurality Problem with Three Colors | 513 |
A Measured Collapse of the Modal μCalculus Alternation Hierarchy | 522 |
Networks III | 534 |
The Complexity of Boolean Constraint Isomorphism | 164 |
Online Competitive Algorithms for Maximizing Weighted Throughput | 187 |
Parallel Prefetching and Caching Is Hard | 211 |
Approximation Algorithms for Minimizing Average Distortion | 234 |
Digraphs Exploration with Little Memory | 246 |
An Algorithmic View on OVSF Code Assignment | 270 |
Periodicity and Unbordered Words | 294 |
Structural Complexity II | 317 |
The Minimal LogicallyDefined NPComplete Problem | 338 |
Simpler Computation of SingleSource Shortest Paths in Linear | 362 |
AutomataBased Analysis of Recursive Cryptographic Protocols | 382 |
A New Model for Selfish Routing | 547 |
Broadcast in the Rendezvous Model | 559 |
Structural Complexity III | 571 |
What Can Be Efficiently Reduced to the KRandom Strings? | 584 |
Regular Language Matching and Other Decidable Cases of | 596 |
Scheduling II | 608 |
The Expected Competitive Ratio for Weighted Completion | 620 |
Algorithmic Information | 632 |
A Lower Bound on the Competitive Ratio of Truthful Auctions | 644 |
Errata to STACS 2003 | 656 |
Other editions - View all
STACS 2004: 21st Annual Symposium on Theoretical Aspects of Computer Science ... Volker Diekert,Michel Habib No preview available - 2014 |
Common terms and phrases
algorithm applications approximation arbitrary assignment assume augmenting Boolean called circuits coloring competitive complexity Computer Computer Science condition consider consists constant constraint construct contains corresponding cost cycle define defined Definition denote determine deterministic different directed distribution edges exactly example exists fact finite first formula function give given graph Hence holds input instance integer introduced known languages lattice layer least Lemma length lower bound machine matching matrix maximum minimal node Note obtain optimal oracle otherwise pair path planar polynomial positive possible present probability problem processing proof properties protocol prove quantum random ratio reduction regular respectively result round running schedule sequence solution space step strategy string structure Theorem Theory tree University upper bound variables vertex vertices weight