STACS 2010 March 4-6, 2010, Nancy, France

27th International Symposium on Theoretical Aspects of Computer Science



Jean-Yves Marion and Thomas Schwentick (Eds.)
ISBN 978-3-939897-16-3, LIPICS Vol. 5 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 7 MB)
Search Publication Server


Authors
  • Adamaszek, Anna
  • Adamaszek, Michal
  • Allamigeon, Xavier
  • Arvind, Vikraman
  • Babai, László
  • Banerjee, Anandam
  • Baswana, Surender
  • Bienkowski, Marcin
  • Björklund, Andreas
  • Bojanczyk, Mikolaj
  • Brandt, Felix
  • Braverman, Vladimir
  • Bravyi, Sergey
  • Bshouty, Nader H.
  • Cai, Jin-Yi
  • Cervelle, Julien
  • Chakraborty, Sourav
  • Chan, Ho-Leung
  • Chechik, Shiri
  • Chen, Victor
  • Chung, Kai-Min
  • Dütting, Paul
  • Das, Bireswar
  • Datta, Samir
  • de Berg, Mark
  • de Wolf, Ronald
  • Dorn, Frederic
  • Doty, David
  • Dumitrescu, Adrian
  • Dyer, Martin
  • Egri, László
  • Epstein, Leah
  • Esparza, Javier
  • Fiala, Jiri
  • Fischer, Eldar
  • Fischer, Felix
  • Fomin, Fedor V.
  • Formenti, Enrico
  • Fortnow, Lance
  • Göller, Stefan
  • Gaiser, Andreas
  • Gaubert, Stéphane
  • Goldberg, Leslie Ann
  • Goubault, Éric
  • Grigorescu, Elena
  • Grigorieff, Serge
  • Gu, Xiaoyang
  • Guillon, Pierre
  • Harrow, Aram W.
  • Hassidim, Avinatan
  • Henzinger, Monika
  • Hirsch, Edward A.
  • Hitchcock, John M.
  • Holzer, Markus
  • Itsykson, Dmitry
  • Jalsenius, Markus
  • Jansen, Maurice
  • Jez, Artur
  • Jez, Lukasz
  • Jiang, Minghui
  • Kaminski, Marcin
  • Kartzow, Alexander
  • Khanna, Neelesh
  • Kiefer, Stefan
  • Klonowski, Marek
  • Korzeniowski, Miroslaw
  • Kowalczyk, Michael
  • Kowalski, Dariusz R.
  • Krokhin, Andrei
  • Kulkarni, Raghav
  • Kuske, Dietrich
  • Lachish, Oded
  • Lam, Tak-Wah
  • Larose, Benoit
  • Lee, Lap-Kei
  • Le Gall, François
  • Levin, Asaf
  • Lidický, Bernard
  • Liu, Zhenming
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Lutz, Jack H.
  • Marion, Jean-Yves
  • Marx, Dániel
  • Mathieu, Claire
  • Mayordomo, Elvira
  • Mazzawi, Hanna
  • Mertzios, George B.
  • Mestre, Julián
  • Mitzenmacher, Michael
  • Montanari, Angelo
  • Naik, Vipul
  • Niedermeier, Rolf
  • Nimbhorkar, Prajakta
  • O'Sullivan, Barry
  • Okhotin, Alexander
  • Ostrovsky, Rafail
  • Patitz, Matthew J.
  • Pattinson, Dirk
  • Paulusma, Daniël
  • Pavan, Aduri
  • Peleg, David
  • Puppis, Gabriele
  • Raman, Venkatesh
  • Razgon, Igor
  • Richard, Gaétan
  • Richerby, David
  • Roditty, Liam
  • Sala, Pietro
  • Sankur, Ocan
  • Sau, Ignasi
  • Saurabh, Saket
  • Scheder, Dominik
  • Schmidt, Jens M.
  • Schröder, Lutz
  • Schudy, Warren
  • Schwentick, Thomas
  • Sciavicco, Guido
  • Segev, Danny
  • Sitters, René
  • Srinivasan, Srikanth
  • Stern, Jacques
  • Summers, Scott M.
  • Tóth, Csaba D.
  • Takhanov, Rustem
  • Tesson, Pascal
  • Ting, Hing-Fung
  • Torán, Jacobo
  • Valarcher, Pierre
  • van Nijnatten, Fred
  • Villanger, Yngve
  • Wagner, Fabian
  • Weber, Ingmar
  • Williams, Ryan
  • Woeginger, Gerhard J.
  • Wolff, Alexander
  • Woods, Damien
  • Yuster, Raphael
  • Zaks, Shmuel

  •   
    Foreword -- 27th International Symposium on Theoretical Aspects of Computer Science
    Authors: Marion, Jean-Yves ; Schwentick, Thomas

    Abstract | Document (67 KB) | BibTeX

    Table of Contents -- 27th International Symposium on Theoretical Aspects of Computer Science
    Authors: Marion, Jean-Yves ; Schwentick, Thomas

    Abstract | Document (134 KB) | BibTeX

    Beyond omega-Regular Languages
    Authors: Bojanczyk, Mikolaj

    Abstract | Document (232 KB) | BibTeX

    Reflections on Multivariate Algorithmics and Problem Parameterization
    Authors: Niedermeier, Rolf

    Abstract | Document (310 KB) | BibTeX

    Mathematics, Cryptology, Security
    Authors: Stern, Jacques

    Abstract | Document (156 KB) | BibTeX

    Large-Girth Roots of Graphs
    Authors: Adamaszek, Anna ; Adamaszek, Michal

    Abstract | Document (295 KB) | BibTeX

    The Tropical Double Description Method
    Authors: Allamigeon, Xavier ; Gaubert, Stéphane ; Goubault, Éric

    Abstract | Document (297 KB) | BibTeX

    The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets
    Authors: Arvind, Vikraman ; Srinivasan, Srikanth

    Abstract | Document (305 KB) | BibTeX

    Evasiveness and the Distribution of Prime Numbers
    Authors: Babai, László ; Banerjee, Anandam ; Kulkarni, Raghav ; Naik, Vipul

    Abstract | Document (311 KB) | BibTeX

    Dynamic Sharing of a Multiple Access Channel
    Authors: Bienkowski, Marcin ; Klonowski, Marek ; Korzeniowski, Miroslaw ; Kowalski, Dariusz R.

    Abstract | Document (292 KB) | BibTeX

    Exact Covers via Determinants
    Authors: Björklund, Andreas

    Abstract | Document (299 KB) | BibTeX

    On Iterated Dominance, Matrix Elimination, and Matched Paths
    Authors: Brandt, Felix ; Fischer, Felix ; Holzer, Markus

    Abstract | Document (300 KB) | BibTeX

    AMS Without 4-Wise Independence on Product Domains
    Authors: Braverman, Vladimir ; Chung, Kai-Min ; Liu, Zhenming ; Mitzenmacher, Michael ; Ostrovsky, Rafail

    Abstract | Document (273 KB) | BibTeX

    Quantum Algorithms for Testing Properties of Distributions
    Authors: Bravyi, Sergey ; Harrow, Aram W. ; Hassidim, Avinatan

    Abstract | Document (300 KB) | BibTeX

    Optimal Query Complexity for Reconstructing Hypergraphs
    Authors: Bshouty, Nader H. ; Mazzawi, Hanna

    Abstract | Document (306 KB) | BibTeX

    Ultimate Traces of Cellular Automata
    Authors: Cervelle, Julien ; Formenti, Enrico ; Guillon, Pierre

    Abstract | Document (326 KB) | BibTeX

    Two-phase Algorithms for the Parametric Shortest Path Problem
    Authors: Chakraborty, Sourav ; Fischer, Eldar ; Lachish, Oded ; Yuster, Raphael

    Abstract | Document (255 KB) | BibTeX

    Continuous Monitoring of Distributed Data Streams over a Time-based Sliding Window
    Authors: Chan, Ho-Leung ; Lam, Tak-Wah ; Lee, Lap-Kei ; Ting, Hing-Fung

    Abstract | Document (317 KB) | BibTeX

    Robust Fault Tolerant Uncapacitated Facility Location
    Authors: Chechik, Shiri ; Peleg, David

    Abstract | Document (298 KB) | BibTeX

    Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation
    Authors: Chen, Victor ; Grigorescu, Elena ; de Wolf, Ronald

    Abstract | Document (131 KB) | BibTeX

    Log-space Algorithms for Paths and Matchings in k-trees
    Authors: Das, Bireswar ; Datta, Samir ; Nimbhorkar, Prajakta

    Abstract | Document (304 KB) | BibTeX

    Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs
    Authors: Das, Bireswar ; Torán, Jacobo ; Wagner, Fabian

    Abstract | Document (311 KB) | BibTeX

    The Traveling Salesman Problem under Squared Euclidean Distances
    Authors: van Nijnatten, Fred ; Sitters, René ; Woeginger, Gerhard J. ; Wolff, Alexander ; de Berg, Mark

    Abstract | Document (329 KB) | BibTeX

    Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs
    Authors: Dorn, Frederic ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Raman, Venkatesh ; Saurabh, Saket

    Abstract | Document (316 KB) | BibTeX

    Planar Subgraph Isomorphism Revisited
    Authors: Dorn, Frederic

    Abstract | Document (321 KB) | BibTeX

    Intrinsic Universality in Self-Assembly
    Authors: Doty, David ; Lutz, Jack H. ; Patitz, Matthew J. ; Summers, Scott M. ; Woods, Damien

    Abstract | Document (317 KB) | BibTeX

    Sponsored Search, Market Equilibria, and the Hungarian Method
    Authors: Dütting, Paul ; Henzinger, Monika ; Weber, Ingmar

    Abstract | Document (303 KB) | BibTeX

    Dispersion in Unit Disks
    Authors: Dumitrescu, Adrian ; Jiang, Minghui

    Abstract | Document (425 KB) | BibTeX

    Long Non-crossing Configurations in the Plane
    Authors: Dumitrescu, Adrian ; Tóth, Csaba D.

    Abstract | Document (317 KB) | BibTeX

    The Complexity of Approximating Bounded-Degree Boolean #CSP
    Authors: Dyer, Martin ; Goldberg, Leslie Ann ; Jalsenius, Markus ; Richerby, David

    Abstract | Document (314 KB) | BibTeX

    The Complexity of the List Homomorphism Problem for Graphs
    Authors: Egri, László ; Krokhin, Andrei ; Larose, Benoit ; Tesson, Pascal

    Abstract | Document (306 KB) | BibTeX

    Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model
    Authors: Epstein, Leah ; Levin, Asaf ; Mestre, Julián ; Segev, Danny

    Abstract | Document (124 KB) | BibTeX

    Computing Least Fixed Points of Probabilistic Systems of Polynomials
    Authors: Esparza, Javier ; Gaiser, Andreas ; Kiefer, Stefan

    Abstract | Document (183 KB) | BibTeX

    The k-in-a-path Problem for Claw-free Graphs
    Authors: Fiala, Jiri ; Kaminski, Marcin ; Lidický, Bernard ; Paulusma, Daniël

    Abstract | Document (304 KB) | BibTeX

    Finding Induced Subgraphs via Minimal Triangulations
    Authors: Fomin, Fedor V. ; Villanger, Yngve

    Abstract | Document (306 KB) | BibTeX

    Inseparability and Strong Hypotheses for Disjoint NP Pairs
    Authors: Fortnow, Lance ; Lutz, Jack H. ; Mayordomo, Elvira

    Abstract | Document (285 KB) | BibTeX

    Branching-time Model Checking of One-counter Processes
    Authors: Göller, Stefan ; Lohrey, Markus

    Abstract | Document (150 KB) | BibTeX

    Evolving Multialgebras Unify All Usual Sequential Computation Models
    Authors: Grigorieff, Serge ; Valarcher, Pierre

    Abstract | Document (317 KB) | BibTeX

    Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
    Authors: Gu, Xiaoyang ; Hitchcock, John M. ; Pavan, Aduri

    Abstract | Document (301 KB) | BibTeX

    Revisiting the Rice Theorem of Cellular Automata
    Authors: Guillon, Pierre ; Richard, Gaétan

    Abstract | Document (299 KB) | BibTeX

    On Optimal Heuristic Randomized Semidecision Procedures, with Application to Proof Complexity
    Authors: Hirsch, Edward A. ; Itsykson, Dmitry

    Abstract | Document (287 KB) | BibTeX

    Weakening Assumptions for Deterministic Subexponential Time Non-Singular Matrix Completion
    Authors: Jansen, Maurice

    Abstract | Document (325 KB) | BibTeX

    On Equations over Sets of Integers
    Authors: Jez, Artur ; Okhotin, Alexander

    Abstract | Document (310 KB) | BibTeX

    Randomized Algorithm for Agreeable Deadlines Packet Scheduling
    Authors: Jez, Lukasz

    Abstract | Document (301 KB) | BibTeX

    Collapsible Pushdown Graphs of Level 2 are Tree-Automatic
    Authors: Kartzow, Alexander

    Abstract | Document (301 KB) | BibTeX

    Approximate Shortest Paths Avoiding a Failed Vertex: Optimal Size Data Structures for Unweighted Graphs
    Authors: Khanna, Neelesh ; Baswana, Surender

    Abstract | Document (330 KB) | BibTeX

    Holant Problems for Regular Graphs with Complex Edge Functions
    Authors: Kowalczyk, Michael ; Cai, Jin-Yi

    Abstract | Document (331 KB) | BibTeX

    Is Ramsey's Theorem omega-automatic?
    Authors: Kuske, Dietrich

    Abstract | Document (315 KB) | BibTeX

    An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem
    Authors: Le Gall, François

    Abstract | Document (316 KB) | BibTeX

    Treewidth Reduction for Constrained Separation and Bipartization Problems
    Authors: Marx, Dániel ; O'Sullivan, Barry ; Razgon, Igor

    Abstract | Document (127 KB) | BibTeX

    Online Correlation Clustering
    Authors: Mathieu, Claire ; Sankur, Ocan ; Schudy, Warren

    Abstract | Document (306 KB) | BibTeX

    The Recognition of Tolerance and Bounded Tolerance Graphs
    Authors: Mertzios, George B. ; Sau, Ignasi ; Zaks, Shmuel

    Abstract | Document (317 KB) | BibTeX

    Decidability of the Interval Temporal Logic ABB over the Natural Numbers
    Authors: Montanari, Angelo ; Puppis, Gabriele ; Sala, Pietro ; Sciavicco, Guido

    Abstract | Document (321 KB) | BibTeX

    Relaxed Spanners for Directed Disk Graphs
    Authors: Peleg, David ; Roditty, Liam

    Abstract | Document (284 KB) | BibTeX

    Unsatisfiable Linear CNF Formulas Are Large and Complex
    Authors: Scheder, Dominik

    Abstract | Document (319 KB) | BibTeX

    Construction Sequences and Certifying 3-Connectedness
    Authors: Schmidt, Jens M.

    Abstract | Document (315 KB) | BibTeX

    Named Models in Coalgebraic Hybrid Logic
    Authors: Schröder, Lutz ; Pattinson, Dirk

    Abstract | Document (130 KB) | BibTeX

    A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
    Authors: Takhanov, Rustem

    Abstract | Document (312 KB) | BibTeX

    Alternation-Trading Proofs, Linear Programming, and Lower Bounds
    Authors: Williams, Ryan

    Abstract | Document (314 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI