STACS 2016 February 17-20, 2016 - Orléans, France

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)



Nicolas Ollinger and Heribert Vollmer (Eds.)
ISBN 978-3-95977-001-9, LIPICS Vol. 47 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 28 MB)
Search Publication Server


Authors
  • Abrahamsen, Mikkel
  • Adamaszek, Anna
  • Agrawal, Akanksha
  • Akshay, S.
  • Angelopoulos, Spyros
  • Anh Quyen, Vuong
  • Antoniadis, Antonios
  • Arora, Rahul
  • Asarin, Eugene
  • Auger, Nicolas
  • Austrin, Per
  • Beyersdorff, Olaf
  • Bhattacharya, Anup
  • Bilò, Davide
  • Bilò, Vittorio
  • Blumensath, Achim
  • Bodirsky, Manuel
  • Bodwin, Greg
  • Bojanczyk, Mikolaj
  • Bonnet, Édouard
  • Brodal, Gerth Stølting
  • Buhrman, Harry
  • Canonne, Clément L.
  • Cervelle, Julien
  • Chandoo, Maurice
  • Chechik, Shiri
  • Chen, Lin
  • Chew, Leroy
  • Colcombet, Thomas
  • Dürr, Christoph
  • Daviaud, Laure
  • Degorre, Aldric
  • de Oliveira Oliveira, Mateus
  • Diakonikolas, Ilias
  • Dima, Catalin
  • Drange, Pål Grønås
  • Dregi, Markus
  • Elberfeld, Michael
  • Fafianie, Stefan
  • Fijalkow, Nathanaël
  • Filmus, Yuval
  • Fomin, Fedor V.
  • Fotakis, Dimitris
  • Garbe, Frederik
  • Gawrychowski, Pawel
  • Genest, Blaise
  • Gittenberger, Bernhard
  • Golebiewski, Zbigniew
  • Golovach, Petr
  • Gouleakis, Themis
  • Gualà, Luciano
  • Gupta, Ashu
  • Gurjar, Rohit
  • Haase, Christoph
  • Hitchcock, John M.
  • Hofman, Piotr
  • Hols, Eva-Maria C.
  • Holub, Štepán
  • Horn, Florian
  • Hrubeš, Pavel
  • I, Tomohiro
  • Inenaga, Shunsuke
  • Jaiswal, Ragesh
  • Jansen, Bart M. P.
  • Jonsson, Peter
  • Köppl, Dominik
  • Kötzing, Timo
  • Kaplan, Haim
  • Karelovic, Bruno
  • Kari, Jarkko
  • Kaski, Petteri
  • Kayal, Neeraj
  • Koivisto, Mikko
  • Korman, Matias
  • Koucký, Michal
  • Kozyakin, Victor
  • Kratsch, Stefan
  • Kreutzer, Stephan
  • Kulkarni, Raghav
  • Kumar, Amit
  • Kumar, Mithilesh
  • Kuperberg, Denis
  • Lampis, Michael
  • Lauria, Massimo
  • Leroux, Jérôme
  • Leucci, Stefano
  • Lidbetter, Thomas
  • Loff, Bruno
  • Lohrey, Markus
  • Lokshtanov, Daniel
  • Lu, Pinyan
  • Lutz, Carsten
  • Mömke, Tobias
  • Mahajan, Meena
  • Manea, Florin
  • Manuel, Amaldev
  • Mary, Arnaud
  • Mavronicolas, Marios
  • Mazowiecki, Filip
  • Milovanov, Alexey
  • Mitchell, Joseph S. B.
  • Mnich, Matthias
  • Mouawad, Amer E.
  • Mycroft, Richard
  • Nair, Vineet
  • Nederlof, Jesper
  • Nicaud, Cyril
  • Okamoto, Yoshio
  • Ollinger, Nicolas
  • Panolan, Fahad
  • Parys, Pawel
  • Paschos, Vangelis Th.
  • Pilipczuk, Marcin
  • Pilipczuk, Michal
  • Pin, Jean-Éric
  • Pivoteau, Carine
  • Podder, Supartha
  • Polishchuk, Valentin
  • Proietti, Guido
  • Räcke, Harald
  • Reidl, Felix
  • Riveros, Cristian
  • Rotenberg, Eva
  • Rubinfeld, Ronitt
  • Sánchez Villaamil, Fernando
  • Saha, Chandan
  • Saurabh, Saket
  • Schirneck, Martin
  • Schmitz, Sylvain
  • Schweitzer, Pascal
  • Shafei, Hadi
  • Shallit, Jeffrey
  • Shukla, Anil
  • Siebertz, Sebastian
  • Sikdar, Somnath
  • Speelman, Florian
  • Stöckel, Morten
  • Stotz, Richard
  • Strozecki, Yann
  • Tewari, Raghunath
  • Thorup, Mikkel
  • Torunczyk, Szymon
  • van Leeuwen, Erik Jan
  • Van Pham, Trung
  • Vassilevska Williams, Virginia
  • Vollmer, Heribert
  • Vyas, Nikhil
  • Wang, Haitao
  • Won Bae, Sang
  • Wrochna, Marcin
  • Yang, Kuan
  • Zamir, Or
  • Zetzsche, Georg
  • Zhang, Chihao
  • Zhang, Guochuan
  • Zwick, Uri

  •   
    Front Matter, Foreword, Conference Organization, External Reviewers, Table of Contents
    Authors: Ollinger, Nicolas ; Vollmer, Heribert

    Abstract | Document (552 KB) | BibTeX

    Ideal Decompositions for Vector Addition Systems (Invited Talk)
    Authors: Leroux, Jérôme ; Schmitz, Sylvain

    Abstract | Document (677 KB) | BibTeX

    Complexity and Expressive Power of Ontology-Mediated Queries (Invited Talk)
    Authors: Lutz, Carsten

    Abstract | Document (630 KB) | BibTeX

    Fine-Grained Algorithms and Complexity (Invited Talk)
    Authors: Vassilevska Williams, Virginia

    Abstract | Document (374 KB) | BibTeX

    Tutorial on Cellular Automata and Tilings (Tutorial)
    Authors: Kari, Jarkko

    Abstract | Document (354 KB) | BibTeX

    Graph Reconstruction with a Betweenness Oracle
    Authors: Abrahamsen, Mikkel ; Bodwin, Greg ; Rotenberg, Eva ; Stöckel, Morten

    Abstract | Document (637 KB) | BibTeX

    Airports and Railways: Facility Location Meets Network Design
    Authors: Adamaszek, Anna ; Antoniadis, Antonios ; Mömke, Tobias

    Abstract | Document (660 KB) | BibTeX

    Simultaneous Feedback Vertex Set: A Parameterized Perspective
    Authors: Agrawal, Akanksha ; Lokshtanov, Daniel ; Mouawad, Amer E. ; Saurabh, Saket

    Abstract | Document (706 KB) | BibTeX

    On Regularity of Unary Probabilistic Automata
    Authors: Akshay, S. ; Genest, Blaise ; Karelovic, Bruno ; Vyas, Nikhil

    Abstract | Document (685 KB) | BibTeX

    The Expanding Search Ratio of a Graph
    Authors: Angelopoulos, Spyros ; Dürr, Christoph ; Lidbetter, Thomas

    Abstract | Document (672 KB) | BibTeX

    Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
    Authors: Arora, Rahul ; Gupta, Ashu ; Gurjar, Rohit ; Tewari, Raghunath

    Abstract | Document (685 KB) | BibTeX

    Entropy Games and Matrix Multiplication Games
    Authors: Asarin, Eugene ; Cervelle, Julien ; Degorre, Aldric ; Dima, Catalin ; Horn, Florian ; Kozyakin, Victor

    Abstract | Document (712 KB) | BibTeX

    Good Predictions Are Worth a Few Comparisons
    Authors: Auger, Nicolas ; Nicaud, Cyril ; Pivoteau, Carine

    Abstract | Document (2,091 KB) | BibTeX

    Dense Subset Sum May Be the Hardest
    Authors: Austrin, Per ; Kaski, Petteri ; Koivisto, Mikko ; Nederlof, Jesper

    Abstract | Document (707 KB) | BibTeX

    Computing the L1 Geodesic Diameter and Center of a Polygonal Domain
    Authors: Won Bae, Sang ; Korman, Matias ; Mitchell, Joseph S. B. ; Okamoto, Yoshio ; Polishchuk, Valentin ; Wang, Haitao

    Abstract | Document (679 KB) | BibTeX

    Are Short Proofs Narrow? QBF Resolution is not Simple
    Authors: Beyersdorff, Olaf ; Chew, Leroy ; Mahajan, Meena ; Shukla, Anil

    Abstract | Document (705 KB) | BibTeX

    Faster Algorithms for the Constrained k-Means Problem
    Authors: Bhattacharya, Anup ; Jaiswal, Ragesh ; Kumar, Amit

    Abstract | Document (712 KB) | BibTeX

    A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games
    Authors: Bilò, Vittorio ; Mavronicolas, Marios

    Abstract | Document (716 KB) | BibTeX

    Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees
    Authors: Bilò, Davide ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido

    Abstract | Document (845 KB) | BibTeX

    On a Fragment of AMSO and Tiling Systems
    Authors: Blumensath, Achim ; Colcombet, Thomas ; Parys, Pawel

    Abstract | Document (661 KB) | BibTeX

    The Complexity of Phylogeny Constraint Satisfaction
    Authors: Bodirsky, Manuel ; Jonsson, Peter ; Van Pham, Trung

    Abstract | Document (592 KB) | BibTeX

    The MSO+U Theory of (N,<) Is Undecidable
    Authors: Bojanczyk, Mikolaj ; Parys, Pawel ; Torunczyk, Szymon

    Abstract | Document (1,107 KB) | BibTeX

    Time-Approximation Trade-offs for Inapproximable Problems
    Authors: Bonnet, Édouard ; Lampis, Michael ; Paschos, Vangelis Th.

    Abstract | Document (700 KB) | BibTeX

    External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates
    Authors: Brodal, Gerth Stølting

    Abstract | Document (714 KB) | BibTeX

    Catalytic Space: Non-determinism and Hierarchy
    Authors: Buhrman, Harry ; Koucký, Michal ; Loff, Bruno ; Speelman, Florian

    Abstract | Document (680 KB) | BibTeX

    Testing Shape Restrictions of Discrete Distributions
    Authors: Canonne, Clément L. ; Diakonikolas, Ilias ; Gouleakis, Themis ; Rubinfeld, Ronitt

    Abstract | Document (810 KB) | BibTeX

    Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace
    Authors: Chandoo, Maurice

    Abstract | Document (676 KB) | BibTeX

    Bottleneck Paths and Trees and Deterministic Graphical Games
    Authors: Chechik, Shiri ; Kaplan, Haim ; Thorup, Mikkel ; Zamir, Or ; Zwick, Uri

    Abstract | Document (668 KB) | BibTeX

    Packing Groups of Items into Multiple Knapsacks
    Authors: Chen, Lin ; Zhang, Guochuan

    Abstract | Document (619 KB) | BibTeX

    Cost Functions Definable by Min/Max Automata
    Authors: Colcombet, Thomas ; Kuperberg, Denis ; Manuel, Amaldev ; Torunczyk, Szymon

    Abstract | Document (637 KB) | BibTeX

    Varieties of Cost Functions
    Authors: Daviaud, Laure ; Kuperberg, Denis ; Pin, Jean-Éric

    Abstract | Document (655 KB) | BibTeX

    Kernelization and Sparseness: the Case of Dominating Set
    Authors: Drange, Pål Grønås ; Dregi, Markus ; Fomin, Fedor V. ; Kreutzer, Stephan ; Lokshtanov, Daniel ; Pilipczuk, Marcin ; Pilipczuk, Michal ; Reidl, Felix ; Sánchez Villaamil, Fernando ; Saurabh, Saket ; Siebertz, Sebastian ; Sikdar, Somnath

    Abstract | Document (731 KB) | BibTeX

    Canonizing Graphs of Bounded Tree Width in Logspace
    Authors: Elberfeld, Michael ; Schweitzer, Pascal

    Abstract | Document (595 KB) | BibTeX

    Preprocessing Under Uncertainty
    Authors: Fafianie, Stefan ; Kratsch, Stefan ; Anh Quyen, Vuong

    Abstract | Document (621 KB) | BibTeX

    Characterisation of an Algebraic Algorithm for Probabilistic Automata
    Authors: Fijalkow, Nathanaël

    Abstract | Document (735 KB) | BibTeX

    Semantic Versus Syntactic Cutting Planes
    Authors: Filmus, Yuval ; Hrubeš, Pavel ; Lauria, Massimo

    Abstract | Document (646 KB) | BibTeX

    Editing to Connected f-Degree Graph
    Authors: Fomin, Fedor V. ; Golovach, Petr ; Panolan, Fahad ; Saurabh, Saket

    Abstract | Document (697 KB) | BibTeX

    Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse
    Authors: Fotakis, Dimitris ; Lampis, Michael ; Paschos, Vangelis Th.

    Abstract | Document (686 KB) | BibTeX

    The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree
    Authors: Garbe, Frederik ; Mycroft, Richard

    Abstract | Document (644 KB) | BibTeX

    Efficiently Finding All Maximal alpha-gapped Repeats
    Authors: Gawrychowski, Pawel ; I, Tomohiro ; Inenaga, Shunsuke ; Köppl, Dominik ; Manea, Florin

    Abstract | Document (659 KB) | BibTeX

    On the Number of Lambda Terms With Prescribed Size of Their De Bruijn Representation
    Authors: Gittenberger, Bernhard ; Golebiewski, Zbigniew

    Abstract | Document (717 KB) | BibTeX

    Tightening the Complexity of Equivalence Problems for Commutative Grammars
    Authors: Haase, Christoph ; Hofman, Piotr

    Abstract | Document (733 KB) | BibTeX

    Autoreducibility of NP-Complete Sets
    Authors: Hitchcock, John M. ; Shafei, Hadi

    Abstract | Document (573 KB) | BibTeX

    A Randomized Polynomial Kernel for Subset Feedback Vertex Set
    Authors: Hols, Eva-Maria C. ; Kratsch, Stefan

    Abstract | Document (623 KB) | BibTeX

    Periods and Borders of Random Words
    Authors: Holub, Štepán ; Shallit, Jeffrey

    Abstract | Document (602 KB) | BibTeX

    Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight
    Authors: Jansen, Bart M. P.

    Abstract | Document (640 KB) | BibTeX

    Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits
    Authors: Kayal, Neeraj ; Nair, Vineet ; Saha, Chandan

    Abstract | Document (743 KB) | BibTeX

    Towards an Atlas of Computational Learning Theory
    Authors: Kötzing, Timo ; Schirneck, Martin

    Abstract | Document (610 KB) | BibTeX

    Quantum Query Complexity of Subgraph Isomorphism and Homomorphism
    Authors: Kulkarni, Raghav ; Podder, Supartha

    Abstract | Document (706 KB) | BibTeX

    Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments
    Authors: Kumar, Mithilesh ; Lokshtanov, Daniel

    Abstract | Document (667 KB) | BibTeX

    Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products
    Authors: Lohrey, Markus ; Zetzsche, Georg

    Abstract | Document (696 KB) | BibTeX

    FPTAS for Hardcore and Ising Models on Hypergraphs
    Authors: Lu, Pinyan ; Yang, Kuan ; Zhang, Chihao

    Abstract | Document (657 KB) | BibTeX

    Efficient Enumeration of Solutions Produced by Closure Operations
    Authors: Mary, Arnaud ; Strozecki, Yann

    Abstract | Document (669 KB) | BibTeX

    Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
    Authors: Mazowiecki, Filip ; Riveros, Cristian

    Abstract | Document (649 KB) | BibTeX

    Algorithmic Statistics, Prediction and Machine Learning
    Authors: Milovanov, Alexey

    Abstract | Document (627 KB) | BibTeX

    Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
    Authors: Mnich, Matthias ; van Leeuwen, Erik Jan

    Abstract | Document (653 KB) | BibTeX

    Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function
    Authors: de Oliveira Oliveira, Mateus

    Abstract | Document (674 KB) | BibTeX

    On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
    Authors: Pilipczuk, Michal ; Wrochna, Marcin

    Abstract | Document (751 KB) | BibTeX

    Improved Approximation Algorithms for Balanced Partitioning Problems
    Authors: Räcke, Harald ; Stotz, Richard

    Abstract | Document (599 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI