Konferenz
STACS 2015: 32nd Symposium on Theoretical Aspects of Computer Science
Beschreibung
The 32nd Symposium on Theoretical Aspects
of Computer Science has been held in München,
Germany at Technische Universität München,
March 4-7, 2015.
Programm
| Wednesday, March 4 | |
| 10:00-13:00 | Tutorial 1 Felix Brandt: Computational Social Choice |
| 13:00-14:00 | Lunch Break |
| 14:00-15:30 | Tutorial 2 Paul Goldberg: Algorithmic Game Theory (1/2) |
| 15:30-15:45 | Coffee Break |
| 15:45-17:15 | Tutorial 2 Paul Goldberg: Algorithmic Game Theory (2/2) |
| 17:30-21:00 | |
| Thursday, March 5 | ||
| 08:15-08:30 | Conference Welcome TUM SVP Hans Pongratz IN GD Georg Carle | |
| 08:30-09:30 | Invited Talk: Manuel Bodirsky "The Complexity of Constraint Satisfaction Problems" | |
| 09:30-10:45 | Session 1A: Computability Chair: Nicolas Ollinger | Session 1B: Graphs Chair: Adi Rosén |
| 09:30-09:55 | Vasco Brattka, Guido Gherardi, and Rupert Hölzl: Las Vegas Computability and Algorithmic Randomness | Takuro Fukunaga: Approximating the Generalized Terminal Backup Problem via Half-integral Multiflow Relaxation |
| 09:55-10:20 | Pablo Castro, Cecilia Kilmurray, and Nir Piterman: Tractable Probabilistic μ-Calculus That Expresses Probabilistic Temporal Logics | Archontia Giannopoulou, and George Mertzios: New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs |
| 10:20-10:45 | Martin Delacourt and Benjamin Hellouin de Ménibus: Construction of μ-Limit Sets of Two-Dimensional Cellular Automata | Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung: On Finding the Adams Consensus Tree |
| 10:45-11:00 | Coffee Break | |
| 11:00-12:40 | Session 2A: Algorithms Chair: Fedor Fomin | Session 2B: Complexity Chair: Till Tantau |
| 11:00-11:25 | Tobias Brunsch, Anna Großwendt, and Heiko Röglin: Solving Totally Unimodular LPs with the Shadow Vertex Algorithm | Eric Allender, Dhiraj Holden, and Valentine Kabanets: The Minimum Oracle Circuit Size Problem |
| 11:25-11:50 | Jan Hązła and Thomas Holenstein: Upper Tail Estimates with Combinatorial Proofs | Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof: Subset Sum in the Absence of Concentration |
| 11:50-12:15 | Stavros Kolliopoulos and Yannis Moysoglou: Extended Formulation Lower Bounds via Hypergraph Coloring? | Martin Avanzini and Ugo Dal Lago: On Sharing, Memoization, and Polynomial Time |
| 12:15-12:40 | Jakub Łącki and Piotr Sankowski: Optimal Decremental Connectivity in Planar Graphs | Olaf Beyersdorff, Leroy Chew, and Mikolas Janota: Proof Complexity of Resolution-based QBF Calculi |
| 12:40-14:00 | Lunch Break | |
| 14:00-15:40 | Session 3A: Algorithms / Online Algorithms Chair: Gilles Schaeffer | Session 3B: Graphs Chair: Johannes Blömer |
| 14:00-14:25 | Jacob Holm and Eva Rotenberg: Dynamic Planar Embeddings of Dynamic Graphs | Saeed Akhoondian Amiri, Lukasz Kaiser, Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz: Graph Searching Games and Width Measures for Directed Graphs |
| 14:25-14:50 | Alejandro López-Ortiz, Marc Renault, and Adi Rosén: Paid Exchanges are Worth the Price | Jean Cardinal, Michael Hoffmann, Vincent Kusters, Csaba D. Toth, and Manuel Wettstein: Arc Diagrams, Flip Distances, and Hamiltonian Triangulations |
| 14:50-15:15 | Andreas Schmid and Jens M. Schmidt: Computing 2-Walks in Polynomial Time | Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, and Girish Varma: Derandomized Graph Product Results Using the Low Degree Long Code |
| 15:15-15:40 | Shai Vardi: The Returning Secretary | Amr Elmasry, Torben Hagerup, and Frank Kammer: Space-Efficient Basic Graph Algorithms |
| 15:40-15:55 | Coffee Break | |
| 15:55-17:35 | Session 4A: Computability Chair: Markus Lohrey | Session 4B: Logic Chair: Marie-Pierre Béal |
| 15:55-16:20 | Anaël Grandjean and Victor Poupet: Comparing 1D and 2D Real Time on Cellular Automata | Rupert Hölzl, Sanjay Jain, and Frank Stephan: Inductive Inference and Reverse Mathematics |
| 16:20-16:45 | Mathieu Hoyrup and Cristobal Rojas: On the Information Carried by Programs about the Objects They Compute | Thomas Place and Marc Zeitoun: Separation and the Successor Relation |
| 16:45-17:10 | Turlough Neary: Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words | Till Tantau: Existential Second-order Logic over Graphs: A Complete Complexity-theoretic Classification |
| 17:10-17:35 | Georg Zetzsche: Computing Downward Closures for Stacked Counter Automata | |
| Friday, March 6 | ||
| 08:45-10:00 | Session 5A: Algorithms and Communication Lower Bounds / Scheduling Chair: Tobias Friedrich | Session 5B: Graphs Chair: Rolf Niedermeier |
| 08:45-09:10 | Arkadev Chattopadhyay and Sagnik Mukhopadhyay: Tribes Is Hard in the Message Passing Model | Telikepalli Kavitha: New Pairwise Spanners |
| 09:10-09:35 | Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang: Communication Complexity of Approximate Matching in Distributed Graphs | Philip N. Klein, Claire Mathieu, and Hang Zhou: Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs |
| 09:35-10:00 | Sungjin Im, Benjamin Moseley, and Kirk Pruhs: Stochastic Scheduling of Heavy-tailed Jobs | Angsheng Li and Pan Peng: Testing Small Set Expansion in General Graphs |
| 10:00-10:15 | Coffee Break | |
| 10:15-11:15 | Invited Talk: Peter Sanders "Parallel Algorithms Reconsidered" | |
| 11:15-12:30 | Session 6A: Algebraic Complexity / Game Theory Chair: Robert Tarjan | Session 6B: Complexity Chair: Takuro Fukunaga |
| 11:15-11:40 | Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino: Markov Decision Processes and Stochastic Games with Total Effective Payoff | Joan Boyar, Lene Favrholdt, Christian Kudahl, and Jesper W. Mikkelsen: Advice Complexity for a Class of Online Problems |
| 11:40-12:05 | Dima Grigoriev and Vladimir Podolskii: Tropical Effective Primary and Dual Nullstellensätze | Johann Brault-Baron, Florent Capelli, and Stefan Mengel: Understanding Model Counting for β-acyclic CNF-formulas |
| 12:05-12:30 | Neeraj Kayal and Chandan Saha: Multi-k-ic Depth Three Circuit Lower Bound | Thomas Colcombet and Amaldev Manuel: Combinatorial Expressions and Lowerbounds |
| 12:30-13:50 | Lunch Break | |
| 14:00-18:30 | Excursion | |
| 19:15-23:15 | Conference Dinner | |
| Saturday, March 7 | ||
| 09:00-10:40 | Session 7A: Algorithms Chair: Martin Dietzfelbinger | Session 7B: Complexity Chair: Heribert Vollmer |
| 09:00-09:25 | Sayan Bhattacharya, Wolfgang Dvořák, Monika Henzinger, and Martin Starnberger: Welfare Maximization with Friends-of-Friends Network Externalities | Esther Galby, Joel Ouaknine, and James Worrell: On Matrix Powering in Low Dimensions |
| 09:25-09:50 | Norbert Bus, Shashwat Garg, Nabil Mustafa, and Saurabh Ray: Improved Local Search for Geometric Hitting Set | Bernd Gärtner and Antonis Thomas: The Complexity of Recognizing Unique Sink Orientations |
| 09:50-10:15 | Markus Chimani and Joachim Spoerhase: Network Design Problems with Bounded Distances via Shallow-Light Steiner Trees | Dmitry Kosolobov: Lempel-Ziv Factorization May Be Harder Than Computing All Runs |
| 10:15-10:40 | Sagi Hed, Haim Kaplan, Andrew Goldberg, and Robert Tarjan: Minimum Cost Flows in Graphs with Unit Capacities | Andreas Krebs, Klaus-Joern Lange, and Michael Ludwig: Visibly Counter Languages and Constant Depth Circuits |
| 10:40-10:55 | Coffee Break | |
| 10:55-12:10 | Session 8A: Fixed Parameter Tractability Chair: Pascal Koiran | Session 8B: Graphs Chair: Dietrich Kuske |
| 10:55-11:20 | Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen: Parameterized Complexity Dichotomy for Steiner Multicut | Pascal Schweitzer: Towards an Isomorphism Dichotomy for Hereditary Graph Classes |
| 11:20-11:45 | Henning Fernau, Florin Manea, Robert Mercas, and Markus L. Schmid: Pattern Matching with Variables:Fast Algorithms and New Hardness Results | Marcin Wrochna: Homomorphism Reconfiguration via Homotopy |
| 11:45-12:10 | Iyad Kanj and Ge Xia: Flip Distance Is in FPT Time O(n+k×ck) | Peter Zeman and Pavel Klavík: Automorphism Groups of Geometrically Represented Graphs |
| 12:10-13:10 | Invited Talk: Sanjeev Arora "Overcoming Intractability in Unsupervised Learning" | |
| 13:10 | End of Conference | |