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