| Schedule |
| Locations |
||
| Garching near Munich Map TUM Campus Garching | ||
| Tutorials, Plenary Talks, Track A | Track B | |
| Interims HS 2 | MI HS 2 | |
| 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 |
|