STACS 2012 February 29th - March 3rd, 2012, Paris, France

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)



Christoph Dürr and Thomas Wilke (Eds.)
ISBN 978-3-939897-35-4, LIPICS Vol. 14 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 28 MB)
Search Publication Server


Authors
  • Abu Zaid, Faried
  • Ambainis, Andris
  • Arnold, André
  • Babai, László
  • Bärtschi, Andreas
  • Bassino, Frédérique
  • Bienvenu, Laurent
  • Bojanczyk, Mikolaj
  • Bonsma, Paul
  • Brázdil, Tomáš
  • Broadbent, Christopher H.
  • Bulatov, Andrei A.
  • Carayol, Arnaud
  • Chan, Timothy M.
  • Chen, Ning
  • Chung, Kai-Min
  • Colcombet, Thomas
  • Datta, Samir
  • David, Julien
  • Diekert, Volker
  • Dietzfelbinger, Martin
  • Doerr, Benjamin
  • Durand-Gasselin, Antoine
  • Durocher, Stephane
  • Dürr, Christoph
  • Dyer, Martin
  • Eggermont, Christian E.J.
  • Elbassioni, Khaled
  • Elberfeld, Michael
  • Feldmann, Andreas Emil
  • Filmus, Yuval
  • Finkel, Olivier
  • Fomin, Fedor V.
  • Foschini, Luca
  • Fournier, Hervé
  • Ganian, Robert
  • Gawrychowski, Pawel
  • Giakkoupis, George
  • Goldberg, Leslie Ann
  • Goldwasser, Shafi
  • Göller, Stefan
  • Golovach, Petr A.
  • Gopalan, Arjun
  • Grädel, Erich
  • Habermehl, Peter
  • Harwath, Frederik
  • Hlineny, Petr
  • Hölzl, Rupert
  • Hoyrup, Mathieu
  • Im, Sungjin
  • Jain, Sanjay
  • Jakoby, Andreas
  • Jansen, Maurice
  • Jerrum, Mark
  • Jez, Artur
  • Kaiser, Lukasz
  • Kaminski, Marcin
  • Kawarabayashi, Ken-ichi
  • Kejlberg-Rasmussen, Casper
  • Kiefer, Stefan
  • Kimura, Kei
  • Kinber, Efim
  • Kobayashi, Yusuke
  • Koutis, Ioannis
  • Kulkarni, Raghav
  • Lam, Henry
  • Langer, Alexander
  • Larsen, Kasper Green
  • Laun, Jürn
  • Levin, Alex
  • Liu, Zhenming
  • Makino, Kazuhisa
  • Malod, Guillaume
  • Mengel, Stefan
  • Merkle, Wolfgang
  • Michalewski, Henryk
  • Miller, Joseph S.
  • Mitsche, Dieter
  • Mitzenmacher, Michael
  • Morrison, Jason
  • Mucha, Marcin
  • Narayanaswamy, N.S.
  • Ngo, Hung Q.
  • Nicaud, Cyril
  • Nies, André
  • Niwinski, Damian
  • Obdržálek, Jan
  • Paluch, Katarzyna
  • Parys, Pawel
  • Peng, Richard
  • Perarnau, Guillem
  • Porat, Ely
  • Qiao, Youming
  • Ramanujan, M.S.
  • Raman, Venkatesh
  • Ravi, R.
  • Rossmanith, Peter
  • Rudra, Atri
  • Santhanam, Rahul
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Schweikardt, Nicole
  • Sikdar, Somnath
  • Sportiello, Andrea
  • Stølting Brodal, Gerth
  • Sun, He
  • Sun, Xiaoming
  • Suri, Subhash
  • Sviridenko, Maxim
  • Tantau, Till
  • Teutsch, Jason
  • Tewari, Raghunath
  • Thilikos, Dimitrios M.
  • Thurley, Marc
  • Torunczyk, Szymon
  • Ushakov, Alexander
  • van der Zwaan, Ruben
  • van Zuylen, Anke
  • Wang, Chengu
  • Ward, Justin
  • Widjaja Lin, Anthony
  • Wilke, Thomas
  • Wilkinson, Bryan T.
  • Winzen, Carola
  • Witt, Carsten
  • Woeginger, Gerhard J.
  • Woelfel, Philipp

  •   
    Frontmatter, Foreword, Conference Organization, External Reviewers, Table of Contents
    Authors: Dürr, Christoph ; Wilke, Thomas

    Abstract | Document (477 KB) | BibTeX

    Forms of Determinism for Automata (Invited Talk)
    Authors: Colcombet, Thomas

    Abstract | Document (966 KB) | BibTeX

    Iterative Methods in Combinatorial Optimization (Invited Talk)
    Authors: Ravi, R.

    Abstract | Document (335 KB) | BibTeX

    On Randomness in Hash Functions (Invited Talk)
    Authors: Dietzfelbinger, Martin

    Abstract | Document (355 KB) | BibTeX

    Pseudo-deterministic Algorithms (Invited Talk)
    Authors: Goldwasser, Shafi

    Abstract | Document (384 KB) | BibTeX

    13/9-approximation for Graphic TSP
    Authors: Mucha, Marcin

    Abstract | Document (587 KB) | BibTeX

    A (k+3)/2-approximation algorithm for monotone submodular k-set packing and general k-exchange systems
    Authors: Ward, Justin

    Abstract | Document (562 KB) | BibTeX

    A Pumping Lemma for Pushdown Graphs of Any Level
    Authors: Parys, Pawel

    Abstract | Document (583 KB) | BibTeX

    Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
    Authors: Elberfeld, Michael ; Jakoby, Andreas ; Tantau, Till

    Abstract | Document (587 KB) | BibTeX

    An Approximation Algorithm for #k-SAT
    Authors: Thurley, Marc

    Abstract | Document (539 KB) | BibTeX

    Asymptotic enumeration of Minimal Automata
    Authors: Bassino, Frédérique ; David, Julien ; Sportiello, Andrea

    Abstract | Document (670 KB) | BibTeX

    Balanced Partitions of Trees and Applications
    Authors: Feldmann, Andreas Emil ; Foschini, Luca

    Abstract | Document (782 KB) | BibTeX

    Cache-Oblivious Implicit Predecessor Dictionaries with the Working-Set Property
    Authors: Stølting Brodal, Gerth ; Kejlberg-Rasmussen, Casper

    Abstract | Document (757 KB) | BibTeX

    Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified
    Authors: Chung, Kai-Min ; Lam, Henry ; Liu, Zhenming ; Mitzenmacher, Michael

    Abstract | Document (649 KB) | BibTeX

    Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P)
    Authors: Jez, Artur

    Abstract | Document (855 KB) | BibTeX

    Concurrency Makes Simple Theories Hard
    Authors: Göller, Stefan ; Widjaja Lin, Anthony

    Abstract | Document (592 KB) | BibTeX

    Conflict-free Chromatic Art Gallery Coverage
    Authors: Bärtschi, Andreas ; Suri, Subhash

    Abstract | Document (622 KB) | BibTeX

    Constant compression and random weights
    Authors: Merkle, Wolfgang ; Teutsch, Jason

    Abstract | Document (473 KB) | BibTeX

    Contraction checking in graphs on surfaces
    Authors: Kaminski, Marcin ; Thilikos, Dimitrios M.

    Abstract | Document (2,362 KB) | BibTeX

    Distribution of the number of accessible states in a random deterministic automaton
    Authors: Carayol, Arnaud ; Nicaud, Cyril

    Abstract | Document (784 KB) | BibTeX

    Edge-disjoint Odd Cycles in 4-edge-connected Graphs
    Authors: Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke

    Abstract | Document (947 KB) | BibTeX

    Efficient algorithms for highly compressed data: The Word Problem in Higman's group is in P
    Authors: Diekert, Volker ; Laun, Jürn ; Ushakov, Alexander

    Abstract | Document (745 KB) | BibTeX

    Efficiently Decodable Compressed Sensing by List-Recoverable Codes and Recursion
    Authors: Ngo, Hung Q. ; Porat, Ely ; Rudra, Atri

    Abstract | Document (646 KB) | BibTeX

    Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
    Authors: Durand-Gasselin, Antoine ; Habermehl, Peter

    Abstract | Document (839 KB) | BibTeX

    Improved Bounds for Bipartite Matching on Surfaces
    Authors: Datta, Samir ; Gopalan, Arjun ; Kulkarni, Raghav ; Tewari, Raghunath

    Abstract | Document (609 KB) | BibTeX

    Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices
    Authors: Koutis, Ioannis ; Levin, Alex ; Peng, Richard

    Abstract | Document (638 KB) | BibTeX

    Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid
    Authors: Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke

    Abstract | Document (747 KB) | BibTeX

    Linear-Space Data Structures for Range Mode Query in Arrays
    Authors: Chan, Timothy M. ; Durocher, Stephane ; Larsen, Kasper Green ; Morrison, Jason ; Wilkinson, Bryan T.

    Abstract | Document (610 KB) | BibTeX

    Log-supermodular functions, functional clones and counting CSPs
    Authors: Bulatov, Andrei A. ; Dyer, Martin ; Goldberg, Leslie Ann ; Jerrum, Mark

    Abstract | Document (613 KB) | BibTeX

    Low Randomness Rumor Spreading via Hashing
    Authors: Giakkoupis, George ; Sauerwald, Thomas ; Sun, He ; Woelfel, Philipp

    Abstract | Document (628 KB) | BibTeX

    Lower Bounds on the Complexity of MSO_1 Model-Checking
    Authors: Ganian, Robert ; Hlineny, Petr ; Langer, Alexander ; Obdržálek, Jan ; Rossmanith, Peter ; Sikdar, Somnath

    Abstract | Document (680 KB) | BibTeX

    LP can be a cure for Parameterized Problems
    Authors: Narayanaswamy, N.S. ; Raman, Venkatesh ; Ramanujan, M.S. ; Saurabh, Saket

    Abstract | Document (654 KB) | BibTeX

    Mind Change Speed-up for Learning Languages from Positive Data
    Authors: Jain, Sanjay ; Kinber, Efim

    Abstract | Document (561 KB) | BibTeX

    Monomials in arithmetic circuits: Complete problems in the counting hierarchy
    Authors: Fournier, Hervé ; Malod, Guillaume ; Mengel, Stefan

    Abstract | Document (880 KB) | BibTeX

    Motion planning with pulley, rope, and baskets
    Authors: Eggermont, Christian E.J. ; Woeginger, Gerhard J.

    Abstract | Document (499 KB) | BibTeX

    On Computing Pareto Stable Assignments
    Authors: Chen, Ning

    Abstract | Document (656 KB) | BibTeX

    On the separation question for tree languages
    Authors: Arnold, André ; Michalewski, Henryk ; Niwinski, Damian

    Abstract | Document (676 KB) | BibTeX

    On the treewidth and related parameters of random geometric graphs
    Authors: Mitsche, Dieter ; Perarnau, Guillem

    Abstract | Document (871 KB) | BibTeX

    Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation
    Authors: Witt, Carsten

    Abstract | Document (625 KB) | BibTeX

    Parameterized Complexity of Connected Even/Odd Subgraph Problems
    Authors: Fomin, Fedor V. ; Golovach, Petr A.

    Abstract | Document (657 KB) | BibTeX

    Playing Mastermind With Constant-Size Memory
    Authors: Doerr, Benjamin ; Winzen, Carola

    Abstract | Document (584 KB) | BibTeX

    Polynomial-time Isomorphism Test for Groups with Abelian Sylow Towers
    Authors: Babai, László ; Qiao, Youming

    Abstract | Document (606 KB) | BibTeX

    Preemptive and Non-Preemptive Generalized Min Sum Set Cover
    Authors: Im, Sungjin ; Sviridenko, Maxim ; van der Zwaan, Ruben

    Abstract | Document (674 KB) | BibTeX

    Randomized Communication Complexity for Linear Algebra Problems over Finite Fields
    Authors: Sun, Xiaoming ; Wang, Chengu

    Abstract | Document (619 KB) | BibTeX

    Regular tree languages, cardinality predicates, and addition-invariant FO
    Authors: Harwath, Frederik ; Schweikardt, Nicole

    Abstract | Document (586 KB) | BibTeX

    Simpler Approximation of the Maximum Asymmetric Traveling Salesman Problem
    Authors: Paluch, Katarzyna ; Elbassioni, Khaled ; van Zuylen, Anke

    Abstract | Document (557 KB) | BibTeX

    Stabilization of Branching Queueing Networks
    Authors: Brázdil, Tomáš ; Kiefer, Stefan

    Abstract | Document (676 KB) | BibTeX

    Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes
    Authors: Jansen, Maurice ; Santhanam, Rahul

    Abstract | Document (613 KB) | BibTeX

    Surface Split Decompositions and Subgraph Isomorphism in Graphs on Surfaces
    Authors: Bonsma, Paul

    Abstract | Document (479 KB) | BibTeX

    The Denjoy alternative for computable functions
    Authors: Bienvenu, Laurent ; Hölzl, Rupert ; Miller, Joseph S. ; Nies, André

    Abstract | Document (630 KB) | BibTeX

    The Determinacy of Context-Free Games
    Authors: Finkel, Olivier

    Abstract | Document (587 KB) | BibTeX

    The dimension of ergodic random sequences
    Authors: Hoyrup, Mathieu

    Abstract | Document (653 KB) | BibTeX

    The Field of Reals is not omega-Automatic
    Authors: Abu Zaid, Faried ; Grädel, Erich ; Kaiser, Lukasz

    Abstract | Document (606 KB) | BibTeX

    The Limits of Decidability for First Order Logic on CPDA Graphs
    Authors: Broadbent, Christopher H.

    Abstract | Document (704 KB) | BibTeX

    The Power of Local Search: Maximum Coverage over a Matroid
    Authors: Filmus, Yuval ; Ward, Justin

    Abstract | Document (528 KB) | BibTeX

    Trichotomy for Integer Linear Systems Based on Their Sign Patterns
    Authors: Kimura, Kei ; Makino, Kazuhisa

    Abstract | Document (544 KB) | BibTeX

    Tying up the loose ends in fully LZW-compressed pattern matching
    Authors: Gawrychowski, Pawel

    Abstract | Document (568 KB) | BibTeX

    Variable time amplitude amplification and quantum algorithms for linear algebra problems
    Authors: Ambainis, Andris

    Abstract | Document (496 KB) | BibTeX

    Weak MSO+U over infinite trees
    Authors: Bojanczyk, Mikolaj ; Torunczyk, Szymon

    Abstract | Document (1,696 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI