STACS 2016: 33th International Symposium on Theoretical Aspects of Computer Science
Veranstaltungsort
Orléans, France
Beschreibung
The 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016) will be held in Orléans, February 17-20, 2016 and is organized by the Laboratoire d'Informatique Fondamentale d'Orléans. The proceedings of the conference will be published in LIPIcs.
STACS 2016 includes a tutorial on Wednesday 17th at 2pm. The contributed and invited talks will be given between Thursday 9am and Saturday 2pm.
Programm
Wednesday, February 17th, 2016
14:00 - 17:30
Tutorial Session chair: Nicolas Ollinger
Jarkko Kari - Tutorial on Cellular Automata and Tilings ↗ⓢ
19:00
Welcome Reception
Thursday, February 18th, 2016
09:00 - 10:00
Plenary Session: Invited Talk chair: Heribert Vollmer
Carsten Lutz - Complexity and Expressive Power of Ontology-Mediated Queries↗ⓢ
Coffee break
10:20 - 11:35
Session 1A chair: Christoph Dürr
Session 1B chair: Michal Pilipczuk
Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster Algorithms for the Constrained k-Means Problem↗
Raghav Kulkarni and Supartha Podder. Quantum Query Complexity of Subgraph Isomorphism and Homomorphism↗
Dimitris Fotakis, Michael Lampis, and Vangelis Th. Paschos. Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse↗
Michael Elberfeld and Pascal Schweitzer. Canonizing Graphs of Bounded Tree Width in Logspace↗
Édouard Bonnet, Michael Lampis, and Vangelis Th. Paschos. Time-Approximation Trade-offs for Inapproximable Problems↗
Mateus de Oliveira Oliveira. Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function↗
Coffee break
11:50 - 12:40
Session 2A chair: Thomas Colcombet
Session 2B chair: Bart M. P. Jansen
S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas. On Regularity of Unary Probabilistic Automata↗
Rahul Arora, Ashu Gupta, Rohit Gurjar, and Raghunath Tewari. Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs↗
Nathanaël Fijalkow. Characterisation of an Algebraic Algorithm for Probabilistic Automata↗
Frederik Garbe and Richard Mycroft. The Complexity of the Hamilton Cycle Problem in Hypergraphs of High Minimum Codegree↗
Lunch
14:10 - 15:25
Session 3A chair: Cyril Nicaud
Session 3B chair: Erik Jan van Leeuwen
Christoph Haase and Piotr Hofman. Tightening the Complexity of Equivalence Problems for Commutative Grammars↗
Akanksha Agrawal, Daniel Lokshtanov, Amer E. Mouawad, and Saket Saurabh. Simultaneous Feedback Vertex Set: A Parameterized Perspective↗
Štěpán Holub and Jeffrey Shallit. Periods and Borders of Random Words↗
Mithilesh Kumar and Daniel Lokshtanov. Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments↗
Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea. Efficiently Finding All Maximal α-gapped Repeats↗
Eva-Maria Hols and Stefan Kratsch. A Randomized Polynomial Kernel for Subset Feedback Vertex Set↗
Coffee break
15:45 - 17:00
Session 4A chair: Marie-Pierre Béal
Session 4B chair: Christophe Paul
Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, and Szymon Toruńczyk. Cost Functions Definable by Min/Max Automata↗
Matthias Mnich and Erik Jan van Leeuwen. Polynomial Kernels for Deletion to Classes of Acyclic Digraphs↗
Laure Daviaud, Denis Kuperberg, and Jean-Éric Pin. Varieties of Cost Functions↗
Bart M. P. Jansen. Constrained Bipartite Vertex Cover: The Easy Kernel is Essentially Tight↗
Filip Mazowiecki and Cristian Riveros. Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties↗
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the case of Dominating Set↗
18:00
Social Event, visit of the Hôtel Groslot
Friday, February 19th, 2016
09:00 - 10:00
Plenary Session: Invited Talk chair: Ioan Todinca
Virginia Vassilevska Williams - Fine-Grained Algorithms and Complexity↗ⓢ
10:20 - 11:35
Session 5A chair: Martin Dietzfelbinger
Session 5B chair: Mathieu Liedloff
Lin Chen and Guochuan Zhang. Packing Groups of Items into Multiple Knapsacks↗
Maurice Chandoo. Deciding Circular-Arc Graph Isomorphism in Parameterized Logspace↗
Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense Subset Sum May Be the Hardest↗
Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh. Editing to Connected f-Degree Graph↗
Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Good Predictions Are Worth a Few Comparisons↗
Michał Pilipczuk and Marcin Wrochna. On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs↗
Coffee break
11:50 - 12:40
Session 6A chair: Jarkko Kari
Session 6B chair: Mathieu Liedloff
Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman. Catalytic Space: Non-determinism and Hierarchy↗
Spyros Angelopoulos, Christoph Dürr, and Thomas Lidbetter. The Expanding Search Ratio of a Graph↗
Eugene Asarin, Julien Cervelle, Aldric Degorre, Cătălin Dima, Florian Horn, and Victor Kozyakin. Entropy Games and Matrix Multiplication Games↗
Stefan Fafianie, Stefan Kratsch, and Vuong Anh Quyen. Preprocessing Under Uncertainty↗
Lunch
14:30 - 15:45
Session 7A chair: Julien Cervelle
Session 7B chair: Matthias Mnich
Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits↗
Harald Räcke and Richard Stotz. Improved Approximation Algorithms for Balanced Partitioning Problems↗
John M. Hitchcock and Hadi Shafei. Autoreducibility of NP-Complete Sets↗
Anna Adamaszek, Antonios Antoniadis, and Tobias Mömke. Airports and Railways: Facility Location Meets Network Design↗
Arnaud Mary and Yann Strozecki. Efficient Enumeration of Solutions Produced by Closure Operations↗
Pinyan Lu, Kuan Yang, and Chihao Zhang. FPTAS for Hardcore and Ising Models on Hypergraphs↗
Coffee break
16:00 - 17:15
Session 8A chair: Pascal Koiran
Session 8B chair: Matthias Mnich
Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction↗
Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph Reconstruction with a Betweenness Oracle↗
Markus Lohrey and Georg Zetzsche. Knapsack in Graph Groups, HNN-Extensions and Amalgamated Products↗
Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, and Uri Zwick. Bottleneck Paths and Trees and Deterministic Graphical Games↗
Vittorio Bilò and Marios Mavronicolas. A Catalog of ∃R-Complete Decision Problems about Nash Equilibria in Multi-Player Games↗
Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-Edge-Fault-Tolerant Approximate Shortest-Path Trees↗
20:00
Conference Dinner at the Restaurant le Week-End
Saturday, February 20th, 2016
09:00 - 10:00
Plenary Session: Invited Talk chair: Nicolas Ollinger
Jérôme Leroux - Ideal Decompositions for Vector Addition Systems↗ⓢ
Coffee break
10:20 - 11:35
Session 9A chair: Markus Lohrey
Session 9B chair: Martin Dietzfelbinger
Mikołaj Bojańczyk, Paweł Parys, and Szymon Toruńczyk. The MSO+U Theory of (N,<) Is Undecidable↗
Gerth Stølting Brodal. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates↗
Achim Blumensath, Thomas Colcombet, and Paweł Parys. On a Fragment of AMSO and Tiling Systems↗
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing Shape Restrictions of Discrete Distributions↗
Bernhard Gittenberger and Zbigniew Gołębiewski. On the Number of Lambda Terms With Prescribed Size of Their De Bruijn Representation↗
Sang Won Bae, Matias Korman, Joseph S.B. Mitchell, Yoshio Okamoto, Valentin Polishchuk, and Haitao Wang. Computing the L1 Geodesic Diameter and Center of a Polygonal Domain↗
Coffee break
11:50 - 12:40
Session 10A chair: Markus Lohrey
Session 10B chair: Nicolas Ollinger
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, and Anil Shukla. Are Short Proofs Narrow? QBF Resolution is not Simple↗
Alexey Milovanov. Algorithmic Statistics, Prediction and Machine Learning↗
Yuval Filmus, Pavel Hrubeš, and Massimo Lauria. Semantic Versus Syntactic Cutting Planes↗
Timo Kötzing and Martin Schirneck. Towards an Atlas of Computational Learning Theory↗
Lunch