STACS '99 Program

Thursday, March 4

9:00 Welcome (Meinel; room A)
9:05 Invited Talk: Nisan: Algorithms for Selfish Agents (Chair: Meinel; room A)
  Coffee Break
  Complexity 1 (Chair: Hromkovic; room A) Theory of Parallel Algorithms 1 (Chair: Widmayer; room B)
10:15 Bernasconi, Shparlinski:
Circuit Complexity of Testing Square-Free Numbers		 Andreev, Clementi, Penna, Rolim:
Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines
10:45 Sauerhoff, Wegener, Werchner:
Relating Branching Program Size and Formula Size over the Full Binary Basis		 Jakoby:
The Average Time Complexity to Compute Prefix Functions in Processor Networks
  Coffee Break
  Complexity 2 (Chair: Hromkovic; room A) Computational Geometry (Chair: Widmayer; room B)
11:45 Cai, Pavan, Sivakumar:
On the Hardness of Permanent		 Joint talk:
  • Icking, Klein, Langetepe:
    An Optimal Competitive Strategy for Walking in Streets
  • Schuierer, Semrau:
    An Optimal Strategy for Searching in Unknown Streets
12:15 Buhrman, Fortnow:
One-sided Versus Two-sided Error in Probabilistic Computation		 Hammar, Nilsson, Schuierer:
Parallel Searching on m Rays
  Lunch
  Complexity 3 (Chair: Köbler; room A) Algorithms and Data Structures 1 (Chair: Albers; room B)
14:30 Lautemann, Schweikardt, Schwentick:
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines		 Kloks, Kratochvíl, Müller:
New Branchwidth Territories
15:00 Durand, Shen, Vereshagin:
Descriptive Complexity of Computable Sequences		 Kao, Lingas, Östlin:
Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions
15:30 Bergman, Slutzki:
Complexity of Some Problems in Universal Algebra		 Bouchitté, Todinca:
Treewidth and Minimum Fill-in of Weakly Triangulated Graphs
  Coffee Break
  Automata and Formal Languages (Chair: Petit; room A) Algorithms and Data Structures 2 (Chair: Kenyon; room B)
16:30 Halava, Hirvensalo, de Wolf:
Decidability and Undecidability of Marked PCP		 Andersson:
An Approximation Algorithm for MAX p-SECTION
17:00 Robson, Diekert:
On Quadratic Word Equations		 Kratsch, Stewart:
Approximating Bandwidth by Mixing Layouts of Interval Graphs
17:30 Kirsten:
Some Undecidability Results Related to the Star Problem in Trace Monoids		 Preis:
Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs
  Visit of the episcopal wine cellars
Reception with the president of the university
Wine-tasting party

Friday, March 5

9:00 Invited Talk: Ossona de Mendez: The Reduced Genus of a Multigraph (Chair: Widmayer; room A)
  Coffee Break
  Complexity 4 (Chair: Esparza; room A) Algorithms and Data Structures 3 (Chair: Silvestri; room B)
10:15 E. Hemaspaandra, L. A. Hemaspaandra, Hempel:
Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries		 Sibeyn:
External Selection
10:45 Arvind, Torán:
Sparse Sets, Approximable Sets, and Parallel Queries to NP		 Ahrendt:
Fast Computations of the Exponential Function
  Coffee Break
  Verification (Chair: Esparza; room A) Algorithms and Data Structures 4 (Chair: Silvestri; room B)
11:45 Koutny, Pappalardo:
A Model of Behaviour Abstraction for Communicating Processes		 Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang:
Constructing Light Spanning Trees with Small Routing Cost
12:15 Bouajjani, Mayr:
Model Checking Lossy Vector Addition Systems		 Nykänen, Ukkonen:
Finding Paths with the Right Cost
  Lunch
  Complexity 5 (Chair: Sgall; room A) Theory of Parallel Algorithms 2 (Chair: Cori; room B)
14:30 Szegedy:
In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved?		 Jakoby, Liskiewicz, Reischuk:
Scheduling Dynamic Graphs
15:00 Frandsen, Hansen, Miltersen:
Lower Bounds for Dynamic Algebraic Problems		 Aiello, Busch, Herlihy, Mavronicolas, Shavit, Touitou:
Supporting Increment and Decrement Operations in Balancing Networks
15:30 Engebretsen:
An Explicit Lower Bound for TSP with Distances One and Two		 Koutsoupias, Papadimitriou:
Worst-case Equilibria
  Coffee Break
  Algorithmic Learning (Chair: Köbler; room A) Logic in Computer Science 1 (Chair: Petit; room B)
16:30 Reischuk, Zeugmann:
A Complete and Tight Average-Case Analysis of Learning Monomials		 Lautemann, McKenzie, Schwentick, Vollmer:
The Descriptive Complexity Approach to LOGCFL
17:00 Case, Chen, Jain:
Costs of General Purpose Learning		 Kupferman, Vardi:
The Weakness of Self-Complementation
17:30 Schuler:
Universal Distributions and Time-bounded Kolmogorov Complexity		 Eiter, Ibaraki, Makino:
On the Difference of Horn Theories
  Guided city tour
Conference dinner

Saturday, March 6

  Complexity 6 (Chair: Sgall; room A) Logic in Computer Science 2 (Chair: Tison; room B)
9:00 Ettinger, Høyer:
On Quantum Algorithms for Noncommutative Hidden Subgroups		 Müller-Olm:
A Modal Fixpoint Logic with Chop
9:30 Sauerhoff:
On the Size of Randomized OBDDs and Read-Once Branching Programs for k-stable Functions		 Barua, Roy, Zhou:
Completeness of Neighbourhood Logic
10:00 Di Crescenzo, Ferguson, Impagliazzo, Jakobsson:
How to Forget a Secret		 Otto:
Eliminating Recursion in the mu-Calculus
  Coffee Break
  Complexity 7 (Chair: Petit; room A) Algorithms and Data Structures 5 (Chair: Albers; room B)
11:00 Messner:
On Optimal Algorithms and Optimal Proof Systems		 Niedermeier, Rossmanith:
Upper Bounds for Vertex Cover - Further Improved
11:30 Esteban, Torán:
Space Bounds for Resolution		 Riedel:
Online Matching for Scheduling Problems
12:15 Invited Talk: Wilke: Classifying Discrete Temporal Properties (Chair: Tison; room A)
  Lunch

See you in Lille for STACS 2000!

The STACS '99 Organizing Committee