************ STACS'2000 -- Call for Participation **************** * STACS'2000 is the 17th International Symposium on Theoretical * * Aspects of Computer Science. * * February 17-19, 2000 -- Lille, FRANCE * * The Early Registration Deadline is January 17 * ****************************************************************** We welcome you to participate in STACS'2000 and the registration fee is quite cheap. To register for STACS'2000 please visit http://www.lifl.fr/stacs2000 email : stacs2000@lifl.fr ****************************************************************** [ Scope ] Algorithms and data structures; Automata and formal languages; Computational and structural complexity; Logic in computer science; Current challenges. [ Conference Site ] The conference will take place in the Ecole Nouvelle d'Ingenieurs en Communication (ENIC). This school is located in the University of Lille I (USTL), in Villeneuve d'Ascq. The University is connected to Lille Town Centre by the underground (metro, or "VAL") system. From Lille, the metro ("VAL"), in the direction of "4 Cantons" will take you directly to the university campus in less than 15 minutes. You get off at the station "Cite Scientifique". By train : TGV trains from Paris (1 hour), London (2h30 hours), Brussels (1 hour) will take you to the centre of Lille (stations "Lille Flandre" or "Lille Europe"). By air : Lille-Lesquin airport or more conveniently Paris Charles de Gaulle airport and then TGV train from Charles de Gaulle airport to the centre of Lille. [ Entry Visa ] (Non EU residents only) Please check with your local French Consulate if you need a visa. Please note that visa applications are made at the French Consulate and may take 4 weeks to process. [ Banquet ] The Conference Dinner will be held on Thursday, Februay 17. It will take place in Lille, in the "Hospice Comtesse". This is a very nice place (the hospice dates from XVII century and contains a museum) in the center of Lille. [ Hotel ] Hotel rooms ranging from two to three stars hotels are available. The hotels are located in Lille center town. For your reservation, please fill the Hotel reservation form (available on the STACS'2000 home page) and send it back before January 17 via surface mail to : Office du tourisme de Lille, Palais Rihour, BP 205, 59205 Lille Cedex, France. [ Registration ] Registration fee is 150 euros or 990 FF (80 euros or 525 FF for students) before January 17, and 195 euros or 1280 FF (110 euros or 720 FF for students) afterwards. 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 C\u{a}t\u{a}lin 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 Jurdzi{\'n}ski Multi-Linearity Self-Testing with Relative Error Fr\'ed\'eric Magniez +Complexity: Nondeterministic Instance Complexity and Hard-to-Prove Tautologies Vikraman Arvind, Johannes K\"obler, Martin Mundhenk, Jacobo Tor\'an 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 Jurdzi{\'n}ski, 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 Hromkovi\v{c}, 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$^{\rm NP}$ and other Lowness results Vikraman Arvind, Johannes K\"obler +Algorithms: An approximation algorithm for the precedence constrained scheduling problem with hierarchical communications Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude K\"onig 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 Gla{\ss}er, 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, Jörg 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) -------------------------------------------------------------------- LUNCH --------------------------------------------------------------------