************ STACS'2000 -- Call for Participation ****************
* STACS'2000 is the 17th International Symposium on Theoretical *
* Aspects of Computer Science. *
* February 17-19, 2000 -- Lille, FRANCE *
******************************************************************
!!! LAST CALL FOR PARTICIPATION !!!
******************************************************************
We welcome you to participate in STACS'2000.
http://www.lifl.fr/stacs2000
email : [EMAIL PROTECTED]
[ Registration ]
Registration fee is 195 euros or 1280 FF (110 euros or 720 FF for
students). The normal registration fee includes sessions attendance,
lunches (February 17-19), morning and afternoon coffee breaks, local
transport, conference dinner on February 17, and STACS'2000
Proceedings. Conference dinner is not included in students
registration fees. Please visit the STACS'2000 home page for the
registration form.
****************** PROGRAMME ***************************************
February 17 th
8:55: Opening
- --------------------------------------------------------------------
9:00-10h : Invited talk
Codes, Graphs, and Algorithms (Amin Shokrollohai)
- --------------------------------------------------------------------
10:05- 10:55
+Algorithms:
On the many faces of block codes
Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B.Sundar Rajan
A New Algorithm for MAX-2-SAT
Edward A. Hirsch
+Complexity:
Bias Invariance of Small Upper Spans
Jack H. Lutz, Martin Strauss
The complexity of planarity testing
Eric Allender, Meena Bhaskar Mahajan
-------------------------------------------------------------------
BREAK
-------------------------------------------------------------------
11:15-12:30
+Automata and formal languages:
About Cube-Free Morphisms
Gw\'ena\"el Richomme, Francis Wlazinski
Linear Cellular Automata with Multiple State Variables
Jarkko Kari
Two variable word equations
Lucian Ilie, Wojciech Plandowski
+Complexity:
Average-Case Quantum Query Complexity
Andris Ambainis, Ronald de Wolf
Tradeoffs between Nondeterminism and Complexity for Communication
Protocols and Branching Programs
Juraj Hromkovi\v{c}, Martin Sauerhoff
The Boolean Hierarchy of NP-Partitions
Sven Kosub, Klaus W. Wagner
------------------------------------------------------------------
LUNCH
------------------------------------------------------------------
14:15-15:30
+Distributed Algorithms:
Binary Exponential Backoff is Stable for High Arrival Rates
Hesham Al-Ammal, Leslie Ann Goldberg, Phil MacKenzie
The Data Broadcast Problem with Preemption
Nicolas Schabanel
An Approximate Lp-Difference Algorithm for Massive Data Streams
Jessica H. Fong, Martin J. Strauss
+Logic:
Succinct representations of model based belief revision
Paolo Penna
Logics Capturing Local Properties
Leonid Libkin
The Complexity of Poor Man's Logic
Edith Hemaspaandra
----------------------------------------------------------------
BREAK
----------------------------------------------------------------
15:50-17:05
+Sorting algorithms:
Fast Integer Sorting in Linear Space
Yijie Han
On the Performance of WEAK-HEAPSORT
Stefan Edelkamp, Ingo Wegener
+Logic:
On the Two-Variable Fragment of the Equational Theory of the Max-Sum
Algebra of the Natural Numbers
Luca Aceto, Zoltan Esik, Anna Ingolfsdottir
Real-time automata and the Kleene algebra of sets of real numbers
Catalin Dima
-------------------------------------------------------------------
FRIDAY February 18 th
-------------------------------------------------------------------
9:00-10 : Invited talk
"A Classification of Symbolic Transition Systems" Tom Henzinger
-------------------------------------------------------------------
10:05- 10:55
+Verification:
Small Progress Measures for Solving Parity Games
Marcin Jurdzinski
Multi-Linearity Self-Testing with Relative Error
Frederic Magniez
+Complexity:
Nondeterministic Instance Complexity and Hard-to-Prove Tautologies
Vikraman Arvind, Johannes Kobler, Martin Mundhenk, Jacobo Toran
Hard Instances of Hard Problems
Jack H. Lutz, Vikram Mhetre, Sridhar Srinivasan
-------------------------------------------------------------------
BREAK
-------------------------------------------------------------------
11:15-12:30
+Verification:
Simulation and Bisimulation over One-Counter Processes
Petr Jancar, Antonin Kucera, Faron Moller
Decidability of reachability problems for classes of two counters
automata
Alain Finkel, Gr�goire Sutre
Hereditary History Preserving Bisimilarity Is Undecidable
Marcin Jurdzinski, Mogens Nielsen
+Approximation algorithms:
The Hardness of Approximating Spanner Problems
Michael Elkin, David Peleg
An Improved Lower Bound on the Approximability of Metric TSP and
Approximation Algorithms for the TSP with Sharpened Triangle
Inequality
Hans-Joachim B�ckenhauer, Juraj Hromkovic, Ralf Klasing,
Sebastian Seibert, Walter Unger
$\lambda$-Coloring of Graphs
Hans L. Bodlaender, Ton Kloks, Jan van Leeuwen, Richard B. Tan
-----------------------------------------------------------------
LUNCH
-----------------------------------------------------------------
14:15-15:30
+Complexity:
Optimal Proof Systems and Sparse Sets
Harry Buhrman, Stephen Fenner, Lance Fortnow, Dieter van Melkebeek
Almost Complete Sets
Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan A. Terwijn
Graph Isomorphism is Low for ZPP^NP and other Lowness results
Vikraman Arvind, Johannes Kobler
+Algorithms:
An approximation algorithm for the precedence constrained scheduling
problem with hierarchical communications
Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude Konig
Polynomial Time Approximation Schemes for the Multiprocessor Open and
Flow Shop Scheduling Problem
Klaus Jansen, Maxim I. Sviridenko
Controlled Conspiracy-2 Search
Ulf Lorenz
---------------------------------------------------------------------
BREAK
---------------------------------------------------------------------
15:50-16:40
+Complexity:
The stability of saturated linear dynamical systems is undecidable
Vincent Blondel, Olivier Bournez, Pascal Koiran, John Tsitsiklis
Tilings: recursivity and regularity
Bruno Durand, Julien Cervelle
15:50-17:05:
+Graph Algorithms:
Listing all potential maximal cliques of a graph
Vincent Bouchitt\'e, Ioan Todinca
Distance Labeling Schemes for Well-Separated Graph Classes
Michal Katz, Nir A. Katz, David Peleg
Pruning graphs with digital search trees. Application to
distance-hereditary graphs.
Jean Marc Lanlignel, Olivier Raynaud, Eric Thierry
---------------------------------------------------------------------
SATURDAY February 19th
---------------------------------------------------------------------
9:00-10:15
+Automata and formal languages:
Characterizing and Deciding MSO-definability of Macro Tree
Transductions
Joost Engelfriet, Sebastian Maneth
Languages of Dot-Depth 3/2
Christian Glasser, Heinz Schmitz
Random Generation and Approximate Counting of Ambiguously Described
Combinatorial Structures
Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini
+On-line Algorithms:
The CNN Problem and Other K-Server Variants
Elias Koutsoupias, David Scot Taylor
The Weighted 2-Server Problem
Marek Chrobak, Jiri Sgall
On the Competitive Ratio of the Work Function Algorithm for the
k-Server Problem
Yair Bartal, Elias Koutsoupias
-------------------------------------------------------------------
BREAK
-------------------------------------------------------------------
10:35-11:25
+Cryptography:
Spectral Bounds on General Hard Core Predicates
Mikael Goldmann, Alexander Russell
Randomness in Visual Cryptography
Annalisa De Bonis, Alfredo De Santis
+Algorithms:
Online Dial-a-Ride Problems: Minimizing the Completion Time
Norbert Ascheuer, Sven Oliver Krumke, Jorg Rambau
The Power Range Assignment Problem in Radio Networks on the Plane
Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri
-----------------------------------------------------------------
11:30 Invited Talk (Pascal Koiran)
Circuits versus trees in algebraic complexity
--------------------------------------------------------------------
LUNCH
--------------------------------------------------------------------
