Front matter
1-15
Algorithms for Selfish Agents
Mechanism Design for Distributed Computation
Noam Nisan
16-31
The Reduced Genus of a Multigraph
Patrice Ossona de Mendez
32-46
Classifying Discrete Temporal Properties
Thomas Wilke
47-56
Circuit Complexity of Testing Square-Free Numbers
Anna Bernasconi and Igor Shparlinski
57-67
Relating Branching Program Size and Formula Size over the Full Binary Basis
Martin Sauerhoff, Ingo Wegener and Ralph Werchner
68-77
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines
Extended Abstract
Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna and José D. P. Rolim
78-89
The Average Time Complexity to Compute Prefix Functions in Processor Networks
Andreas Jakoby
90-99
On the Hardness of Permanent
Jin-Yi Cai, A. Pavan and D. Sivakumar
100-109
One-Sided Versus Two-Sided Error in Probabilistic Computation
Harry Buhrman and Lance Fortnow
110-120
An Optimal Competitive Strategy for Walking in Streets
Christian Icking, Rolf Klein and Elmar Langetepe
121-131
An Optimal Strategy for Searching in Unknown Streets
Sven Schuierer and Ines Semrau
132-142
Parallel Searching on
m
Rays
Mikael Hammar, Bengt J. Nilsson and Sven Schuierer
143-152
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
Clemens Lautemann, Nicole Schweikardt and Thomas Schwentick
153-162
Descriptive Complexity of Computable Sequences
Bruno Durand, Alexander Shen and Nikolai Vereshagin
163-172
Complexity of Some Problems in Universal Algebra
Extended Abstract
Clifford Bergman and Giora Slutzki
173-183
New Branchwidth Territories
Ton Kloks, Jan Kratochvíl and Haiko Müller
184-196
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions
Ming-Yang Kao, Andrzej Lingas and Anna Östlin
197-206
Treewidth and Minimum Fill-In of Weakly Triangulated Graphs
Vincent Bouchitté and Ioan Todinca
207-216
Decidability and Undecidability of Marked PCP
Vesa Halava, Mika Hirvensalo and Ronald de Wolf
217-226
On Quadratic Word Equations
John Michael Robson and Volker Diekert
227-236
Some Undecidability Results Related to the Star Problem in Trace Monoids
Extended Abstract
Daniel Kirsten
237-247
An Approximation Algorithm for Max
p
-Section
Gunnar Andersson
248-258
Approximating Bandwidth by Mixing Layouts of Interval Graphs
Dieter Kratsch and Lorna Stewart
259-269
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs
Robert Preis
270-280
Extending Downward Collapse from 1-versus-2 Queries to
j
-versus-
j
+ 1 Queries
Edith Hemaspaandra, Lane. A. Hemaspaandra and Harald Hempel
281-290
Sparse Sets, Approximable Sets, and Parallel Queries to NP
Vikraman Arvind and Jacobo Torán
291-301
External Selection
Jop F. Sibeyn
302-312
Fast Computations of the Exponential Function
Timm Ahrendt
313-322
A Model of Behaviour Abstraction for Communicating Processes
Maciej Koutny and Giuseppe Pappalardo
323-333
Model Checking Lossy Vector Addition Systems
Ahmed Bouajjani and Richard Mayr
334-344
Constructing Light Spanning Trees with Small Routing Cost
Bang Ye Wu, Kun-Mao Chao and Chuan Yi Tang
345-355
Finding Paths with the Right Cost
Matti Nykänen and Esko Ukkonen
356-361
In How Many Steps the
k
Peg Version of the Towers of Hanoi Game Can Be Solved?
Mario Szegedy
362-372
Lower Bounds for Dynamic Algebraic Problems
Gudmund Skovbjerg Frandsen, Johan P. Hansen and Peter Bro Miltersen
373-382
An Explicit Lower Bound for TSP with Distances One and Two
Lars Engebretsen
383-392
Scheduling Dynamic Graphs
Andreas Jakoby, Maciej Liśkiewicz and Rüdiger Reischuk
393-403
Supporting Increment and Decrement Operations in Balancing Networks
William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas and Nir Shavit, et al.
404-413
Worst-Case Equilibria
Elias Koutsoupias and Christos Papadimitriou
414-423
A Complete and Tight Average-Case Analysis of Learning Monomials
Rüdiger Reischuk and Thomas Zeugmann
424-433
Costs of General Purpose Learning
John Case, Keh-Jiann Chen and Sanjay Jain
434-443
Universal Distributions and Time-Bounded Kolmogorov Complexity
Rainer Schuler
444-454
The Descriptive Complexity Approach to LOGCFL
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick and Heribert Vollmer
455-466
The Weakness of Self-Complementation
Orna Kupferman and Moshe Y. Vardi
467-477
On the Difference of Horn Theories
Extended Abstract
Thomas Eiter, Toshihide Ibaraki and Kazuhisa Makino
478-487
On Quantum Algorithms for Noncommutative Hidden Subgroups
Mark Ettinger and Peter Høyer
488-499
On the Size of Randomized OBDDs and Read-Once Branching Programs for
k
-Stable Functions
Martin Sauerhoff
500-509
How To Forget a Secret
Extended Abstract
Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo and Markus Jakobsson
510-520
A Modal Fixpoint Logic with Chop
Markus Müller-Olm
521-530
Completeness of Neighbourhood Logic
Rana Barua, Suman Roy and Zhou Chaochen
531-540
Eliminating Recursion in the μ-Calculus
Martin Otto
541-550
On Optimal Algorithms and Optimal Proof Systems
Jochen Messner
551-560
Space Bounds for Resolution
Juan Luis Esteban and Jacobo Torán
561-570
Upper Bounds for Vertex Cover Further Improved
Rolf Niedermeier and Peter Rossmanith
571-580
Online Matching for Scheduling Problems
Marco Riedel
Back matter