Portal - STACS 2016

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

Brodal, Gerth Stølting

de Oliveira Oliveira, Mateus

Gittenberger, Bernhard

Golebiewski, Zbigniew

Mitchell, Joseph S. B.

Paschos, Vangelis Th.

Sánchez Villaamil, Fernando

van Leeuwen, Erik Jan

Van Pham, Trung

Vassilevska Williams, Virginia

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 | Privacy Published by LZI

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