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