Garching near Munich    Map TUM Campus Garching
Tutorials, Plenary Talks, Track A Track B
Interims HS 2 MI HS 2


Wednesday, March 4

Tutorial 1  Felix Brandt: Computational Social Choice

13:00-14:00 Lunch Break

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 Welcome Reception


Thursday, March 5
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
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
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
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
Stavros Kolliopoulos and Yannis Moysoglou: Extended Formulation Lower Bounds via Hypergraph Coloring? Martin Avanzini and Ugo Dal Lago: On Sharing, Memoization, and Polynomial Time
Jakub Łącki and Piotr SankowskiOptimal Decremental Connectivity in Planar Graphs Olaf Beyersdorff, Leroy Chew, and Mikolas JanotaProof 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
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
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
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
Shai Vardi: The Returning Secretary Amr Elmasry, Torben Hagerup, and Frank Kammer: Space-Efficient Basic Graph Algorithms
Coffee Break
Session 4A: Computability
Chair: Markus Lohrey
Session 4B: Logic
Chair: Marie-Pierre Béal
Anaël Grandjean and Victor Poupet: Comparing 1D and 2D Real Time on Cellular Automata Rupert Hölzl, Sanjay Jain, and Frank StephanInductive Inference and Reverse Mathematics
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
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
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 KavithaNew 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
Sungjin Im, Benjamin Moseley, and Kirk PruhsStochastic Scheduling of Heavy-tailed Jobs Angsheng Li and Pan PengTesting 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
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
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
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
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
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 SchweitzerTowards 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
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
Invited Talk: Sanjeev Arora "Overcoming Intractability in Unsupervised Learning"
End of Conference