[UAI] STACS 2000: Program and registration

From: Marc.Tommasi@lifl.fr
Date: Thu Jan 06 2000 - 08:35:58 PST

  • Next message: Larranaga Mugica Pedro: "[UAI] technical reports"

    ************ 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.
                  http://www.lifl.fr/stacs2000
                   email : stacs2000@lifl.fr

     The registration fee is quite cheap.

    [ 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
    --------------------------------------------------------------------



    This archive was generated by hypermail 2b29 : Thu Jan 06 2000 - 08:44:17 PST