20. STACS 2003: Berlin, Germany

Helmut Alt, Michel Habib (Eds.): STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings. Lecture Notes in Computer Science 2607 Springer 2003, ISBN 3-540-00623-0 BibTeX

@proceedings{DBLP:conf/stacs/2003,
  editor    = {Helmut Alt and
               Michel Habib},
  title     = {STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer
               Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings},
  booktitle = {STACS},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {2607},
  year      = {2003},
  isbn      = {3-540-00623-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Invited Papers

Victor Vianu:
Logic as a Query Language: From Frege to XML. 1-12
Electronic Edition (Springer LINK) BibTeX
Alain Viari:
How Does Computer Science Change Molecular Biology? 13
Electronic Edition (Springer LINK) BibTeX

Contributed Papers

Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun:
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer. 14-25
Electronic Edition (Springer LINK) BibTeX
Ileana Streinu, Sue Whitesides:
Rectangle Visibility Graphs: Characterization, Construction, and Compaction. 26-37
Electronic Edition (Springer LINK) BibTeX
Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel H. M. Smid, Norbert Zeh:
Approximating Geometric Bottleneck Shortest Paths. 38-49
Electronic Edition (Springer LINK) BibTeX
Stefan Langerman, William L. Steiger:
Optimization in Arrangements. 50-61
Electronic Edition (Springer LINK) BibTeX
Pascal Tesson, Denis Thérien:
Complete Classifications for the Communication Complexity of Regular Languages. 62-73
Electronic Edition (Springer LINK) BibTeX
Juhani Karhumäki, Michel Latteux, Ion Petre:
The Commutation with Codes and Ternary Sets of Words. 74-84
Electronic Edition (Springer LINK) BibTeX
Guillem Godoy, Ashish Tiwari, Rakesh M. Verma:
On the Confluence of Linear Shallow Term Rewrite Systems. 85-96
Electronic Edition (Springer LINK) BibTeX
Victor L. Selivanov:
Wadge Degrees of omega-Languages of Deterministic Turing Machines. 97-108
Electronic Edition (Springer LINK) BibTeX
Dariusz R. Kowalski, Andrzej Pelc:
Faster Deterministic Broadcasting in Ad Hoc Radio Networks. 109-120
Electronic Edition (Springer LINK) BibTeX
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Private Computations in Networks: Topology versus Randomness. 121-132
Electronic Edition (Springer LINK) BibTeX
Thomas Erlebach, Stamatis Stefanakos:
On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements. 133-144
Electronic Edition (Springer LINK) BibTeX
Claus-Peter Schnorr:
Lattice Reduction by Random Sampling and Birthday Methods. 145-156
Electronic Edition (Springer LINK) BibTeX
Qi Cheng:
On the Ultimate Complexity of Factorials. 157-166
Electronic Edition (Springer LINK) BibTeX
Xizhong Zheng, Robert Rettinger, Burchard von Braunmühl:
On the Effective Jordan Decomposability. 167-178
Electronic Edition (Springer LINK) BibTeX
Lucian Ilie, Baozhen Shan, Sheng Yu:
Fast Algorithms for Extended Regular Expression Matching and Searching. 179-190
Electronic Edition (Springer LINK) BibTeX
Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen:
Algorithms for Transposition Invariant String Matching. 191-202
Electronic Edition (Springer LINK) BibTeX
Anton Mityagin:
On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets. 203-211
Electronic Edition (Springer LINK) BibTeX
Harry Buhrman, Lance Fortnow, Aduri Pavan:
Some Results on Derandomization. 212-222
Electronic Edition (Springer LINK) BibTeX
Eike Kiltz:
On the Representation of Boolean Predicates of the Diffie-Hellman Function. 223-233
Electronic Edition (Springer LINK) BibTeX
Peter Høyer, Robert Spalek:
Quantum Circuits with Unbounded Fan-out. 234-246
Electronic Edition (Springer LINK) BibTeX
Marek Chrobak, Jiri Sgall:
Analysis of the Harmonic Algorithm for Three Servers. 247-259
Electronic Edition (Springer LINK) BibTeX
Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha:
Non-clairvoyant Scheduling for Minimizing Mean Slowdown. 260-270
Electronic Edition (Springer LINK) BibTeX
Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis:
Space Efficient Hash Tables with Worst Case Constant Access Time. 271-282
Electronic Edition (Springer LINK) BibTeX
Hervé Brönnimann, Frédéric Cazals, Marianne Durand:
Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure. 283-294
Electronic Edition (Springer LINK) BibTeX
Beate Bollig:
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs. 295-306
Electronic Edition (Springer LINK) BibTeX
Martin Sauerhoff:
Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs. 307-318
Electronic Edition (Springer LINK) BibTeX
Petr Hlinený:
Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids. 319-330
Electronic Edition (Springer LINK) BibTeX
Ricard Gavaldà, Denis Thérien:
Algebraic Characterizations of Small Classes of Boolean Functions. 331-342
Electronic Edition (Springer LINK) BibTeX
John Hershberger, Subhash Suri, Amit M. Bhosle:
On the Difficulty of Some Shortest Path Problems. 343-354
Electronic Edition (Springer LINK) BibTeX
Tomás Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy:
Representing Graph Metrics with Fewest Edges. 355-366
Electronic Edition (Springer LINK) BibTeX
Tomás Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, Rina Panigrahy:
Computing Shortest Paths with Uncertainty. 367-378
Electronic Edition (Springer LINK) BibTeX
Andrei A. Krokhin, Benoit Larose:
Solving Order Constraints in Logarithmic Space. 379-390
Electronic Edition (Springer LINK) BibTeX
Vasco Brattka:
The Inversion Problem for Computable Linear Operators. 391-402
Electronic Edition (Springer LINK) BibTeX
Markus Bläser:
Algebras of Minimal Rank over Arbitrary Fields. 403-414
Electronic Edition (Springer LINK) BibTeX
Oliver Giel, Ingo Wegener:
Evolutionary Algorithms and the Maximum Matching Problem. 415-426
Electronic Edition (Springer LINK) BibTeX
Piotr Sankowski:
Alternative Algorithms for Counting All Matchings in Graphs. 427-438
Electronic Edition (Springer LINK) BibTeX
Robert W. Irving, David Manlove, Sandy Scott:
Strong Stability in the Hospitals/Residents Problem. 439-450
Electronic Edition (Springer LINK) BibTeX
Arnaud Durand, Miki Hermann:
The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete. 451-462
Electronic Edition (Springer LINK) BibTeX
Dietrich Kuske, Markus Lohrey:
Decidable Theories of Cayley-Graphs. 463-474
Electronic Edition (Springer LINK) BibTeX
Stefan Szeider:
The Complexity of Resolution with Generalized Symmetry Rules. 475-486
Electronic Edition (Springer LINK) BibTeX
Amin Coja-Oghlan, Anusch Taraz:
Colouring Random Graphs in Expected Polynomial Time. 487-498
Electronic Edition (Springer LINK) BibTeX
Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse:
An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation. 499-510
Electronic Edition (Springer LINK) BibTeX
Amin Coja-Oghlan:
Finding Large Independent Sets in Polynomial Expected Time. 511-522
Electronic Edition (Springer LINK) BibTeX
Peter Damaschke:
Distributed Soft Path Coloring. 523-534
Electronic Edition (Springer LINK) BibTeX
Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara:
Competing Provers Yield Improved Karp-Lipton Collapse Results. 535-546
Electronic Edition (Springer LINK) BibTeX
Harry Buhrman, Richard Chang, Lance Fortnow:
One Bit of Advice. 547-558
Electronic Edition (Springer LINK) BibTeX
Marcus Schaefer, Frank Stephan:
Strong Reductions and Immunity for Exponential Time. 559-570
Electronic Edition (Springer LINK) BibTeX
Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. 571-582
Electronic Edition (Springer LINK) BibTeX
Wil Michiels, Jan H. M. Korst, Emile H. L. Aarts, Jan van Leeuwen:
Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem. 583-595
Electronic Edition (Springer LINK) BibTeX
Malik Magdon-Ismail, Costas Busch, Mukkai S. Krishnamoorthy:
Cake-Cutting Is Not a Piece of Cake. 596-607
Electronic Edition (Springer LINK) BibTeX
Kunal Talwar:
The Price of Truth: Frugality in Truthful Mechanisms. 608-619
Electronic Edition (Springer LINK) BibTeX
Patricia Bouyer:
Untameable Timed Automata! 620-631
Electronic Edition (Springer LINK) BibTeX
Nicolas Ollinger:
The Intrinsic Universality Problem of One-Dimensional Cellular Automata. 632-641
Electronic Edition (Springer LINK) BibTeX
Julien Cervelle, Enrico Formenti:
On Sand Automata. 642-653
Electronic Edition (Springer LINK) BibTeX
Amr Elmasry, Michael L. Fredman:
Adaptive Sorting and the Information Theoretic Lower Bound. 654-662
Electronic Edition (Springer LINK) BibTeX
Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov:
A Discrete Subexponential Algorithm for Parity Games. 663-674
Electronic Edition (Springer LINK) BibTeX
Michael Backes, Christian Jacobi:
Cryptographically Sound and Machine-Assisted Verification of Security Protocols. 675-686
Electronic Edition (Springer LINK) BibTeX
Véronique Bruyère, Emmanuel Dall'Olio, Jean-François Raskin:
Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic. 687-698
Electronic Edition (Springer LINK) BibTeX