default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID22nd STACS 2005: Stuttgart, Germany
- Volker Diekert, Bruno Durand:
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
Invited Talks
- Manindra Agrawal, Nitin Saxena
:
Automorphisms of Finite Rings and Applications to Complexity of Problems. 1-17 - Mireille Bousquet-Mélou:
Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages. 18-35 - Uwe Schöning:
Algorithmics in Exponential Time. 36-43
Session 1 A
- Carsten Witt:
Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics. 44-56 - Petros Drineas, Ravi Kannan, Michael W. Mahoney:
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. 57-68 - Nir Andelman, Yossi Azar, Motti Sorani:
Truthful Approximation Mechanisms for Scheduling Selfish Related Machines. 69-82
Session 1B
- Lidia Tendera:
Counting in the Two Variable Guarded Logic with Transitivity. 83-96 - Dietmar Berwanger, Giacomo Lenzi:
The Variable Hierarchy of the µ-Calculus Is Strict. 97-109
Session 2A
- Manuel Bodirsky:
The Core of a Countably Categorical Structure. 110-120 - Guillaume Theyssier:
How Common Can Be Universality for Cellular Automata?. 121-132 - Victor Poupet:
Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods. 133-144
Session 2B
- Tomás Brázdil, Antonín Kucera, Oldrich Strazovský:
On the Decidability of Temporal Properties of Probabilistic Pushdown Automata. 145-157 - Detlef Kähler, Ralf Küsters, Thomas Wilke:
Deciding Properties of Contract-Signing Protocols. 158-169
Session 3A
- Christian Glaßer:
Polylog-Time Reductions Decrease Dot-Depth. 170-181 - Frank Harary, Wolfgang Slany, Oleg Verbitsky:
On the Computational Complexity of the Forcing Chromatic Number. 182-193 - Lars Engebretsen, Jonas Holmerin:
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP. 194-205
Session 3B
- Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks:
Three Optimal Algorithms for Balls of Three Colors. 206-217 - Xiang-Yang Li, Zheng Sun, Weizhao Wang:
Cost Sharing and Strategyproof Mechanisms for Set Cover Games. 218-230 - Petra Berenbrink, Tom Friedetzky, Zengjian Hu, Russell A. Martin:
On Weighted Balls-into-Bins Games. 231-243
Session 3B
- Gregorio Malajovich, Klaus Meer:
Computing Minimal Multi-homogeneous Bézout Numbers Is Hard. 244-255 - Volker Weber, Thomas Schwentick:
Dynamic Complexity Theory Revisited. 256-268 - Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia:
Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. 269-280
Session 4B
- Sasanka Roy, Sandip Das, Subhas C. Nandy:
Shortest Monotone Descent Path Problem in Polyhedral Terrain. 281-292 - Markus Schmidt:
Packet Buffering: Randomization Beats Deterministic Algorithms. 293-304 - Abraham Flaxman, Bartosz Przydatek:
Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. 305-314
Session 5A
- Hubie Chen:
Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. 315-326 - Michael Benedikt, Luc Segoufin:
Regular Tree Languages Definable in FO. 327-339 - Kousha Etessami, Mihalis Yannakakis:
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. 340-352
Session 5B
- Josep Díaz, Xavier Pérez-Giménez, Maria J. Serna, Nicholas C. Wormald:
Connectivity for Wireless Agents Moving on a Cycle or Grid. 353-364 - Marcin Bienkowski, Miroslaw Dynia, Miroslaw Korzeniowski:
Improved Algorithms for Dynamic Page Migration. 365-376 - Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang:
Approximate Range Mode and Range Median Queries. 377-388
Session 6A
- Emmanuel Jeandel:
Topological Automata. 389-398 - Gregor Gramlich, Georg Schnitger:
Minimizing NFA's and Regular Expressions. 399-411
Session 6B
- Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin:
Increasing Kolmogorov Complexity. 412-421 - Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank Stephan:
Kolmogorov-Loveland Randomness and Stochasticity. 422-433
Session 7A
- Nir Ailon, Bernard Chazelle:
Information Theory in Property Testing and Monotonicity Testing in Higher Dimension. 434-447 - Vittorio Bilò, Michele Flammini, Luca Moscardelli:
On Nash Equilibria in Non-cooperative All-Optical Networks. 448-459 - Nikhil Bansal, Kirk Pruhs:
Speed Scaling to Manage Temperature. 460-471
Session 7B
- Vikraman Arvind, T. C. Vijayaraghavan:
The Complexity of Solving Linear Equations over a Finite Ring. 472-484 - Michael Kaminski:
A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields. 485-495 - Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid:
Characterizing TC0 in Terms of Infinite Groups. 496-507
Session 8A
- Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid:
Fast Pruning of Geometric Spanners. 508-520 - Gerard Jennhwa Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng:
The PIGs Full Monty - A Floor Show of Minimal Separators. 521-532 - Ulrik Brandes, Daniel Fleischer:
Centrality Measures Based on Current Flow. 533-544
Session 8B
- Fabio Burderi, Antonio Restivo:
Varieties of Codes and Kraft Inequality. 545-556 - Eran Rom, Amnon Ta-Shma:
Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes. 557-568 - Michal Kunc:
The Power of Commuting with Finite Sets of Words. 569-580
Session 9A
- Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto:
Exact Quantum Algorithms for the Leader Election Problem. 581-592 - Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf:
Robust Polynomials and Quantum Algorithms. 593-604 - Gus Gutoski, John Watrous:
Quantum Interactive Proofs with Competing Provers. 605-616
Session 9B
- Benjamin Doerr:
Roundings Respecting Hard Constraints. 617-628 - Gianni Franceschini:
Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves. 629-640 - Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni:
Cycle Cover with Short Cycles. 641-653
Session 10A
- Telikepalli Kavitha, Kurt Mehlhorn:
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs. 654-665 - Surender Baswana, Vishrut Goyal, Sandeep Sen:
All-Pairs Nearly 2-Approximate Shortest-Paths in O(n2 polylog n) Time. 666-679
Session 10B
- Massimiliano Goldwurm, Violetta Lonati:
Pattern Occurrences in Multicomponent Models. 680-692 - Graham P. Oliver, Richard M. Thomas:
Automatic Presentations for Finitely Generated Groups. 693-704
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-20 00:13 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
