22. STACS 2005: Stuttgart, Germany

Volker Diekert, Bruno Durand (Eds.): STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings. Lecture Notes in Computer Science 3404 Springer 2005, ISBN 3-540-24998-2 BibTeX

Invited Talks

Manindra Agrawal, Nitin Saxena:
Automorphisms of Finite Rings and Applications to Complexity of Problems. 1-17
Electronic Edition (link) BibTeX
Mireille Bousquet-Mélou:
Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages. 18-35
Electronic Edition (link) BibTeX
Uwe Schöning:
Algorithmics in Exponential Time. 36-43
Electronic Edition (link) BibTeX

Session 1 A

Carsten Witt:
Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics. 44-56
Electronic Edition (link) BibTeX
Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. 57-68
Electronic Edition (link) BibTeX
Nir Andelman, Yossi Azar, Motti Sorani:
Truthful Approximation Mechanisms for Scheduling Selfish Related Machines. 69-82
Electronic Edition (link) BibTeX

Session 1B

Lidia Tendera:
Counting in the Two Variable Guarded Logic with Transitivity. 83-96
Electronic Edition (link) BibTeX
Dietmar Berwanger, Giacomo Lenzi:
The Variable Hierarchy of the µ-Calculus Is Strict. 97-109
Electronic Edition (link) BibTeX

Session 2A

Manuel Bodirsky:
The Core of a Countably Categorical Structure. 110-120
Electronic Edition (link) BibTeX
Guillaume Theyssier:
How Common Can Be Universality for Cellular Automata?. 121-132
Electronic Edition (link) BibTeX
Victor Poupet:
Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods. 133-144
Electronic Edition (link) BibTeX

Session 2B

Tomás Brázdil, Antonín Kucera, Oldrich Strazovský:
On the Decidability of Temporal Properties of Probabilistic Pushdown Automata. 145-157
Electronic Edition (link) BibTeX
Detlef Kähler, Ralf Küsters, Thomas Wilke:
Deciding Properties of Contract-Signing Protocols. 158-169
Electronic Edition (link) BibTeX

Session 3A

Christian Glaßer:
Polylog-Time Reductions Decrease Dot-Depth. 170-181
Electronic Edition (link) BibTeX
Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number. 182-193
Electronic Edition (link) BibTeX
Lars Engebretsen, Jonas Holmerin:
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP. 194-205
Electronic Edition (link) BibTeX

Session 3B

Zdenek Dvorak, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks:
Three Optimal Algorithms for Balls of Three Colors. 206-217
Electronic Edition (link) BibTeX
Xiang-Yang Li, Zheng Sun, Weizhao Wang:
Cost Sharing and Strategyproof Mechanisms for Set Cover Games. 218-230
Electronic Edition (link) BibTeX
Petra Berenbrink, Tom Friedetzky, Zengjian Hu, Russell A. Martin:
On Weighted Balls-into-Bins Games. 231-243
Electronic Edition (link) BibTeX

Session 3B

Gregorio Malajovich, Klaus Meer:
Computing Minimal Multi-homogeneous Bézout Numbers Is Hard. 244-255
Electronic Edition (link) BibTeX
Volker Weber, Thomas Schwentick:
Dynamic Complexity Theory Revisited. 256-268
Electronic Edition (link) BibTeX
Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia:
Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. 269-280
Electronic Edition (link) BibTeX

Session 4B

Sasanka Roy, Sandip Das, Subhas C. Nandy:
Shortest Monotone Descent Path Problem in Polyhedral Terrain. 281-292
Electronic Edition (link) BibTeX
Markus Schmidt:
Packet Buffering: Randomization Beats Deterministic Algorithms. 293-304
Electronic Edition (link) BibTeX
Abraham Flaxman, Bartosz Przydatek:
Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. 305-314
Electronic Edition (link) BibTeX

Session 5A

Hubie Chen:
Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. 315-326
Electronic Edition (link) BibTeX
Michael Benedikt, Luc Segoufin:
Regular Tree Languages Definable in FO. 327-339
Electronic Edition (link) BibTeX
Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. 340-352
Electronic Edition (link) BibTeX

Session 5B

Josep Díaz-Giménez, Xavier Pérez, Maria J. Serna, Nicholas C. Wormald:
Connectivity for Wireless Agents Moving on a Cycle or Grid. 353-364
Electronic Edition (link) BibTeX
Marcin Bienkowski, Miroslaw Dynia, Miroslaw Korzeniowski:
Improved Algorithms for Dynamic Page Migration. 365-376
Electronic Edition (link) BibTeX
Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang:
Approximate Range Mode and Range Median Queries. 377-388
Electronic Edition (link) BibTeX

Session 6A

Emmanuel Jeandel:
Topological Automata. 389-398
Electronic Edition (link) BibTeX
Gregor Gramlich, Georg Schnitger:
Minimizing NFA's and Regular Expressions. 399-411
Electronic Edition (link) BibTeX

Session 6B

Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. 412-421
Electronic Edition (link) BibTeX
Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank Stephan:
Kolmogorov-Loveland Randomness and Stochasticity. 422-433
Electronic Edition (link) BibTeX

Session 7A

Nir Ailon, Bernard Chazelle:
Information Theory in Property Testing and Monotonicity Testing in Higher Dimension. 434-447
Electronic Edition (link) BibTeX
Vittorio Bilò, Michele Flammini, Luca Moscardelli:
On Nash Equilibria in Non-cooperative All-Optical Networks. 448-459
Electronic Edition (link) BibTeX
Nikhil Bansal, Kirk Pruhs:
Speed Scaling to Manage Temperature. 460-471
Electronic Edition (link) BibTeX

Session 7B

Vikraman Arvind, T. C. Vijayaraghavan:
The Complexity of Solving Linear Equations over a Finite Ring. 472-484
Electronic Edition (link) BibTeX
Michael Kaminski:
A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields. 485-495
Electronic Edition (link) BibTeX
Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid:
Characterizing TC⁰ in Terms of Infinite Groups. 496-507
Electronic Edition (link) BibTeX

Session 8A

Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid:
Fast Pruning of Geometric Spanners. 508-520
Electronic Edition (link) BibTeX
Gerard Jennhwa Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng:
The PIGs Full Monty - A Floor Show of Minimal Separators. 521-532
Electronic Edition (link) BibTeX
Ulrik Brandes, Daniel Fleischer:
Centrality Measures Based on Current Flow. 533-544
Electronic Edition (link) BibTeX

Session 8B

Fabio Burderi, Antonio Restivo:
Varieties of Codes and Kraft Inequality. 545-556
Electronic Edition (link) BibTeX
Eran Rom, Amnon Ta-Shma:
Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes. 557-568
Electronic Edition (link) BibTeX
Michal Kunc:
The Power of Commuting with Finite Sets of Words. 569-580
Electronic Edition (link) BibTeX

Session 9A

Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto:
Exact Quantum Algorithms for the Leader Election Problem. 581-592
Electronic Edition (link) BibTeX
Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. 593-604
Electronic Edition (link) BibTeX
Gus Gutoski, John Watrous:
Quantum Interactive Proofs with Competing Provers. 605-616
Electronic Edition (link) BibTeX

Session 9B

Benjamin Doerr:
Roundings Respecting Hard Constraints. 617-628
Electronic Edition (link) BibTeX
Gianni Franceschini:
Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves. 629-640
Electronic Edition (link) BibTeX
Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni:
Cycle Cover with Short Cycles. 641-653
Electronic Edition (link) BibTeX

Session 10A

Telikepalli Kavitha, Kurt Mehlhorn:
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs. 654-665
Electronic Edition (link) BibTeX
Surender Baswana, Vishrut Goyal, Sandeep Sen:
All-Pairs Nearly 2-Approximate Shortest-Paths in O(n² polylog n) Time. 666-679
Electronic Edition (link) BibTeX

Session 10B

Massimiliano Goldwurm, Violetta Lonati:
Pattern Occurrences in Multicomponent Models. 680-692
Electronic Edition (link) BibTeX
Graham P. Oliver, Richard M. Thomas:
Automatic Presentations for Finitely Generated Groups. 693-704
Electronic Edition (link) BibTeX