STACS 2013 February 27 - March 2, 2013, Kiel, Germany

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)



Natacha Portier and Thomas Wilke (Eds.)
ISBN 978-3-939897-50-7, LIPICS Vol. 20 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 25 MB)
Search Publication Server

Authors
  • Abel, Zachary
  • Ambainis, Andris
  • Atserias, Albert
  • Baartse, Martijn
  • Backurs, Arturs
  • Barba, Luis
  • Ben-Amram, Amir M.
  • Bilu, Yonatan
  • Björklund, Andreas
  • Bojanczyk, Mikolaj
  • Bousquet, Nicolas
  • Braverman, Mark
  • Cannon, Sarah
  • Capelli, Florent
  • Case, Adam
  • Chen, Danny Z.
  • Chen, Xi
  • Clément, Julien
  • Colcombet, Thomas
  • Cygan, Marek
  • Daniely, Amit
  • Darnstädt, Malte
  • Dartois, Luc
  • Daviaud, Laure
  • de Wolf, Ronald
  • Demaine, Erik D.
  • Demaine, Martin L.
  • Durand, Arnaud
  • Dyer, Martin
  • Dósa, György
  • Eisenstat, Sarah
  • Epstein, Leah
  • Etessami, Kousha
  • Fomin, Fedor V.
  • Francois, Nathanael
  • Gaspers, Serge
  • Gawrychowski, Pawel
  • Goldberg, Leslie Ann
  • Grandoni, Fabrizio
  • Hemaspaandra, Edith
  • Hemaspaandra, Lane A.
  • Huschenbett, Martin
  • Idziaszek, Tomasz
  • Ishai, Yuval
  • Iwata, Yoichi
  • Jalsenius, Markus
  • Jeandel, Emmanuel
  • Jeong, Jisu
  • Jerrum, Mark
  • Jez, Artur
  • Karbasi, Amin
  • Kaski, Petteri
  • Kavitha, Telikepalli
  • Klauck, Hartmut
  • Klimann, Ines
  • Kociumaka, Tomasz
  • Komarath, Balagopal
  • Korman, Matias
  • Kowalik, Lukasz
  • Kratsch, Stefan
  • Kufleitner, Manfred
  • Kushilevitz, Eyal
  • Kutzkov, Konstantin
  • Kwon, O-joung
  • Lagoutte, Aurélie
  • Langerman, Stefan
  • Lauser, Alexander
  • Levin, Asaf
  • Linial, Nati
  • Lokshtanov, Daniel
  • Lu, Pinyan
  • Lubiw, Anna
  • Lutz, Jack H.
  • Ma, Tengyu
  • Magniez, Frédéric
  • Magnin, Loïck
  • Makarychev, Konstantin
  • Manea, Florin
  • Marx, Dániel
  • McQuillan, Colin
  • Meer, Klaus
  • Mehlhorn, Kurt
  • Mengel, Stefan
  • Menton, Curtis
  • Mercas, Robert
  • Nasre, Meghana
  • Nguyen Thi, Thu Hien
  • Nowotka, Dirk
  • Oliva, Sergi
  • Ordyniak, Sebastian
  • Oshri, Gal
  • Oum, Sang-il
  • Paperman, Charles
  • Patitz, Matthew J.
  • Paulusma, Daniel
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Porat, Benny
  • Portier, Natacha
  • Radoszewski, Jakub
  • Ramanujan, M. S.
  • Richerby, David
  • Roland, Jérémie
  • Rytter, Wojciech
  • Sach, Benjamin
  • Sadakane, Kunihiko
  • Saks, Michael
  • Sankowski, Piotr
  • Sarma, Jayalal M. N.
  • Saurabh, Saket
  • Schulz, André
  • Schweller, Robert T.
  • Segev, Danny
  • Sgall, Jiri
  • Silveira, Rodrigo I.
  • Simon, Hans Ulrich
  • Skrzypczak, Michal
  • Slivovsky, Friedrich
  • Smotrovs, Juris
  • Souvaine, Diane L.
  • Strulovich, Omer
  • Stéphan, Thomassé
  • Summers, Scott M
  • Szeider, Stefan
  • Szwast, Wieslaw
  • Szörényi, Balázs
  • Tang, Bo
  • Tendera, Lidia
  • Thilikos, Dimitrios M.
  • Tiseanu, Catalin
  • Vallée, Brigitte
  • van Leeuwen, Erik Jan
  • Vanier, Pascal
  • Viglietta, Giovanni
  • Villanger, Yngve
  • Wahlström, Magnus
  • Wang, Haitao
  • Wang, Yajun
  • Watson, Thomas
  • Weimann, Oren
  • Wilke, Thomas
  • Winslow, Andrew
  • Yoshida, Yuichi
  • Zadimoghaddam, Morteza
    		•

    		  
    Frontmatter, Table of Contents, Preface, Workshop Organization
    Authors: Portier, Natacha ; Wilke, Thomas

    Abstract | Document (504 KB) | BibTeX

    The complexity of analyzing infinite-state Markov chains, Markov decision processes, and stochastic games (Invited talk)
    Authors: Etessami, Kousha

    Abstract | Document (344 KB) | BibTeX

    Graph coloring, communication complexity and the stubborn problem (Invited talk)
    Authors: Bousquet, Nicolas ; Lagoutte, Aurélie ; Stéphan, Thomassé

    Abstract | Document (390 KB) | BibTeX

    Physarum Computations (Invited talk)
    Authors: Mehlhorn, Kurt

    Abstract | Document (364 KB) | BibTeX

    Algorithmic Graph Structure Theory (Tutorial)
    Authors: Marx, Dániel

    Abstract | Document (321 KB) | BibTeX

    Searching for better fill-in
    Authors: Fomin, Fedor V. ; Villanger, Yngve

    Abstract | Document (829 KB) | BibTeX

    Probably Optimal Graph Motifs
    Authors: Björklund, Andreas ; Kaski, Petteri ; Kowalik, Lukasz

    Abstract | Document (653 KB) | BibTeX

    Tight bounds for Parameterized Complexity of Cluster Editing
    Authors: Fomin, Fedor V. ; Kratsch, Stefan ; Pilipczuk, Marcin ; Pilipczuk, Michal ; Villanger, Yngve

    Abstract | Document (665 KB) | BibTeX

    Bounded-width QBF is PSPACE-complete
    Authors: Atserias, Albert ; Oliva, Sergi

    Abstract | Document (521 KB) | BibTeX

    Model Counting for CNF Formulas of Bounded Modular Treewidth
    Authors: Paulusma, Daniel ; Slivovsky, Friedrich ; Szeider, Stefan

    Abstract | Document (630 KB) | BibTeX

    Backdoors to q-Horn
    Authors: Gaspers, Serge ; Ordyniak, Sebastian ; Ramanujan, M. S. ; Saurabh, Saket ; Szeider, Stefan

    Abstract | Document (701 KB) | BibTeX

    On Polynomial Kernels for Sparse Integer Linear Programs
    Authors: Kratsch, Stefan

    Abstract | Document (620 KB) | BibTeX

    Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
    Authors: Fomin, Fedor V. ; Lokshtanov, Daniel ; Saurabh, Saket ; Thilikos, Dimitrios M.

    Abstract | Document (819 KB) | BibTeX

    The PCP theorem for NP over the reals
    Authors: Baartse, Martijn ; Meer, Klaus

    Abstract | Document (563 KB) | BibTeX

    Mutual Dimension
    Authors: Case, Adam ; Lutz, Jack H.

    Abstract | Document (547 KB) | BibTeX

    Exact and Approximation Algorithms for the Maximum Constraint Satisfaction Problem over the Point Algebra
    Authors: Iwata, Yoichi ; Yoshida, Yuichi

    Abstract | Document (597 KB) | BibTeX

    Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
    Authors: Makarychev, Konstantin

    Abstract | Document (580 KB) | BibTeX

    The complexity of approximating conservative counting CSPs
    Authors: Chen, Xi ; Dyer, Martin ; Goldberg, Leslie Ann ; Jerrum, Mark ; Lu, Pinyan ; McQuillan, Colin ; Richerby, David

    Abstract | Document (652 KB) | BibTeX

    Lossy Chains and Fractional Secret Sharing
    Authors: Ishai, Yuval ; Kushilevitz, Eyal ; Strulovich, Omer

    Abstract | Document (635 KB) | BibTeX

    Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM
    Authors: Cannon, Sarah ; Demaine, Erik D. ; Demaine, Martin L. ; Eisenstat, Sarah ; Patitz, Matthew J. ; Schweller, Robert T. ; Summers, Scott M ; Winslow, Andrew

    Abstract | Document (850 KB) | BibTeX

    Unlabeled Data Does Provably Help
    Authors: Darnstädt, Malte ; Simon, Hans Ulrich ; Szörényi, Balázs

    Abstract | Document (622 KB) | BibTeX

    Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
    Authors: Pilipczuk, Michal

    Abstract | Document (601 KB) | BibTeX

    On Pairwise Spanners
    Authors: Cygan, Marek ; Grandoni, Fabrizio ; Kavitha, Telikepalli

    Abstract | Document (629 KB) | BibTeX

    Excluded vertex-minors for graphs of linear rank-width at most k.
    Authors: Jeong, Jisu ; Kwon, O-joung ; Oum, Sang-il

    Abstract | Document (670 KB) | BibTeX

    Recompression: a simple and powerful technique for word equations
    Authors: Jez, Artur

    Abstract | Document (532 KB) | BibTeX

    Fast Algorithms for Abelian Periods in Words and Greatest Common Divisor Queries
    Authors: Kociumaka, Tomasz ; Radoszewski, Jakub ; Rytter, Wojciech

    Abstract | Document (684 KB) | BibTeX

    Finding Pseudo-repetitions
    Authors: Gawrychowski, Pawel ; Manea, Florin ; Mercas, Robert ; Nowotka, Dirk ; Tiseanu, Catalin

    Abstract | Document (603 KB) | BibTeX

    Algorithms for Designing Pop-Up Cards
    Authors: Abel, Zachary ; Demaine, Erik D. ; Demaine, Martin L. ; Eisenstat, Sarah ; Lubiw, Anna ; Schulz, André ; Souvaine, Diane L. ; Viglietta, Giovanni ; Winslow, Andrew

    Abstract | Document (1,285 KB) | BibTeX

    Space-Time Trade-offs for Stack-Based Algorithms
    Authors: Barba, Luis ; Korman, Matias ; Langerman, Stefan ; Silveira, Rodrigo I. ; Sadakane, Kunihiko

    Abstract | Document (672 KB) | BibTeX

    L_1 Shortest Path Queries among Polygonal Obstacles in the Plane
    Authors: Chen, Danny Z. ; Wang, Haitao

    Abstract | Document (616 KB) | BibTeX

    Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
    Authors: Kufleitner, Manfred ; Lauser, Alexander

    Abstract | Document (546 KB) | BibTeX

    FO^2 with one transitive relation is decidable
    Authors: Szwast, Wieslaw ; Tendera, Lidia

    Abstract | Document (723 KB) | BibTeX

    Two-variable first order logic with modular predicates over words
    Authors: Dartois, Luc ; Paperman, Charles

    Abstract | Document (749 KB) | BibTeX

    Abusing the Tutte Matrix: An Algebraic Instance Compression for the K-set-cycle Problem
    Authors: Wahlström, Magnus

    Abstract | Document (564 KB) | BibTeX

    Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs
    Authors: Pilipczuk, Marcin ; Pilipczuk, Michal ; Sankowski, Piotr ; van Leeuwen, Erik Jan

    Abstract | Document (627 KB) | BibTeX

    The arithmetic complexity of tensor contractions
    Authors: Capelli, Florent ; Durand, Arnaud ; Mengel, Stefan

    Abstract | Document (607 KB) | BibTeX

    Search versus Decision for Election Manipulation Problems
    Authors: Hemaspaandra, Edith ; Hemaspaandra, Lane A. ; Menton, Curtis

    Abstract | Document (572 KB) | BibTeX

    Improved Bounds for Online Preemptive Matching
    Authors: Epstein, Leah ; Levin, Asaf ; Segev, Danny ; Weimann, Oren

    Abstract | Document (692 KB) | BibTeX

    Parameterized Matching in the Streaming Model
    Authors: Jalsenius, Markus ; Porat, Benny ; Sach, Benjamin

    Abstract | Document (670 KB) | BibTeX

    Popular Matchings: Structure and Cheating Strategies
    Authors: Nasre, Meghana

    Abstract | Document (573 KB) | BibTeX

    Fooling One-Sided Quantum Protocols
    Authors: Klauck, Hartmut ; de Wolf, Ronald

    Abstract | Document (570 KB) | BibTeX

    Explicit relation between all lower bound techniques for quantum query complexity
    Authors: Magnin, Loïck ; Roland, Jérémie

    Abstract | Document (738 KB) | BibTeX

    Optimal quantum query bounds for almost all Boolean functions
    Authors: Ambainis, Andris ; Backurs, Arturs ; Smotrovs, Juris ; de Wolf, Ronald

    Abstract | Document (582 KB) | BibTeX

    Streaming Complexity of Checking Priority Queues
    Authors: Francois, Nathanael ; Magniez, Frédéric

    Abstract | Document (685 KB) | BibTeX

    Deterministic algorithms for skewed matrix products
    Authors: Kutzkov, Konstantin

    Abstract | Document (587 KB) | BibTeX

    The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems
    Authors: Ma, Tengyu ; Tang, Bo ; Wang, Yajun

    Abstract | Document (620 KB) | BibTeX

    Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type
    Authors: Jeandel, Emmanuel ; Vanier, Pascal

    Abstract | Document (731 KB) | BibTeX

    The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
    Authors: Klimann, Ines

    Abstract | Document (634 KB) | BibTeX

    Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
    Authors: Ben-Amram, Amir M.

    Abstract | Document (589 KB) | BibTeX

    On the practically interesting instances of MAXCUT
    Authors: Bilu, Yonatan ; Daniely, Amit ; Linial, Nati ; Saks, Michael

    Abstract | Document (712 KB) | BibTeX

    First Fit bin packing: A tight analysis
    Authors: Dósa, György ; Sgall, Jiri

    Abstract | Document (572 KB) | BibTeX

    Constrained Binary Identification Problem
    Authors: Karbasi, Amin ; Zadimoghaddam, Morteza

    Abstract | Document (583 KB) | BibTeX

    Regular languages of thin trees
    Authors: Bojanczyk, Mikolaj ; Idziaszek, Tomasz ; Skrzypczak, Michal

    Abstract | Document (563 KB) | BibTeX

    Approximate comparison of distance automata
    Authors: Colcombet, Thomas ; Daviaud, Laure

    Abstract | Document (617 KB) | BibTeX

    The Rank of Tree-Automatic Linear Orderings
    Authors: Huschenbett, Martin

    Abstract | Document (594 KB) | BibTeX

    A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms
    Authors: Clément, Julien ; Nguyen Thi, Thu Hien ; Vallée, Brigitte

    Abstract | Document (631 KB) | BibTeX

    Search using queries on indistinguishable items
    Authors: Braverman, Mark ; Oshri, Gal

    Abstract | Document (572 KB) | BibTeX

    Pebbling, Entropy and Branching Program Size Lower Bounds
    Authors: Komarath, Balagopal ; Sarma, Jayalal M. N.

    Abstract | Document (562 KB) | BibTeX

    Advice Lower Bounds for the Dense Model Theorem
    Authors: Watson, Thomas

    Abstract | Document (597 KB) | BibTeX

    Author Index
    Authors: Portier, Natacha ; Wilke, Thomas

    Abstract | Document (68 KB) | BibTeX

    		  



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