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 SquareFree 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:

12:15  Buhrman, Fortnow: Onesided Versus Twosided 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 Fillin 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 pSECTION 
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/2Approximation Algorithm for Maximum Weighted Matching in General Graphs 
Visit of the episcopal wine cellars Reception with the president of the university Winetasting 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 1versus2 Queries to jversusj+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, KunMao 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: Worstcase 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 AverageCase 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 SelfComplementation 
17:30  Schuler: Universal Distributions and Timebounded 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üllerOlm: A Modal Fixpoint Logic with Chop 
9:30  Sauerhoff: On the Size of Randomized OBDDs and ReadOnce Branching Programs for kstable 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 muCalculus 
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 