Schedule
Jump to: [Tuesday] [Wednesday] [Thursday] [Friday]
Click to pre-conference workshop
Monday, March 03 (pre-conference workshop)
13.30 - 14.30
The Complexity of Enumerating Satisfying Assignments
(invited talk)
14.30 - 15.00
Coffee break
15.00 - 16.20
Contributed talks 1
Reducing Stochastic Games to Semidefinite Programming
Graph Neural Networks and Arithmetic Circuits
The complexity of computing the period and the exponent of a digraph
Optimal Proof Systems for Complex Sets are Hard to Find
16.20 - 16.50
Coffee break
16.50 - 17.50
Contributed talks 2
Dynamics of Schelling Games
Hereditary First-Order Logic and Extensional ESO
Rejection in Abstract Argumentation: Harder Than Acceptance?
18.00 - 18.30
Business Meeting of the GI groups
Tuesday, March 04 (pre-conference workshop)
09.15 - 10.15
Quicksort, Timsort, Powersort - Algorithmic ideas, engineering tricks, and trivia behind CPython’s new sorting algorithm
(invited talk)
10.15 - 10.45
Coffee break
10.45 - 12.05
Contributed talks 3
On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
Parameterized Complexity of Segment Routing
On the Tightness of the Standard Lower Bound in the Two-Machine Routing Open Shop
Categorizing Ensembles of Real-Valued Functions
12.05 - 13.30
Lunch break
Tuesday, March 04
13.30 - 14.30
Opening
13.40 - 14.30
14.30 - 15.00
Coffee break
15.00 - 15.10
Address of the president of Friedrich Schiller University Jena
15.10 - 16.00
16.00 - 16.30
Coffee break
16.30 - 17.50
Distributed algorithms and communication
Chair: Sebastian Wild
Logic and complexity
Chair: Manuel Bodirsky
Being Efficient in Time, Space, and Workload: a Self-stabilizing Unison and its Consequences
Tropical Proof Systems: Between R(CP) and Resolution
Local Density and its Distributed Approximation
On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure
The Complexity of Learning LTL, CTL and ATL formulas
Card-Based Protocols Imply PSM Protocols
Generalized Arrival on Tree-Like Multigraphs
18.30 - 23.00
Reception (Volkshaus)
Wednesday, March 05
09.15 - 10.15
A Strongly Polynomial Algorithm for Linear Programs with at most Two Non-zero Entries per Row or Column
(invited talk)
Chair: Nguyen Kim Thang
10.15 - 10.45
Coffee break
10.45 - 12.05
Resilience and robustness
Chair: Magnus Wahlström
Algebra, logic and computability
Chair: Andrei Bulatov
Protecting the Connectivity of a Graph under Non-uniform Edge Failures
Monotone weak distributive laws over the lifted powerset monad in categories of algebras
A Deterministic Approach to Shortest Path Restoration in Edge Faulty Graphs
Identity-Preserving Lax Extensions and Where to Find Them
A Note on Approximation of Spanning Tree Congestion
How to play the Accordion: Uniformity and the (non-)conservativity of the linear approximation of the λ-calculus
Cycle Counting under Local Differential Privacy for Degeneracy-bounded Graphs
Computability of extender sets in multidimensional subshifts
12.05 - 13.30
Lunch break
13.30 - 15.10
Parameterized algorithms I
Chair: Arne Meier
Automata
Chair: Sylvain Schmitz
Parameterized Saga of First-Fit and Last-Fit Coloring
Alternating hierarchy of subshifts defined by nondeterministic plane-walking automata
Faster algorithms on linear delta-matroids
On Cascades of Reset Automata
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
Commutative N-rational series of polynomial growth
MaxMin Separation Problems: FPT Algorithms for st-Separator and Odd Cycle Transversal
Efficiently computing the minimum rank of a matrix in a monoid of zero-one matrices
Polynomial kernel and incompressibility for Prison-Free Edge Deletion and Completion
Slightly non-linear higher-order tree transducers (online)
15.10 - 15.40
Coffee break
15.40 - 17.20
Parameterized algorithms II
Chair: Nils Morawietz
Computational geometry and scheduling
Chair: Christian Komusiewicz
Residue Domination in Bounded-Treewidth Graphs
Dynamic Unit-Disk Range Reporting
Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances
Dominating Set, Independent Set, Discrete k-Center, Dispersion, and Related Problems for Planar Points in Convex Position
Can You Link Up With Treewidth?
Approximating Densest Subgraph in Geometric Intersection Graphs
Metric Dimension and Geodetic Set Parameterized by Vertex Cover
Efficient approximation schemes for scheduling on a stochastic number of machines
Multivariate Exploration of Metric Dilation
Minimizing the Number of Tardy Jobs with Uniform Processing Times on Parallel Machines
17.30 - 18.30
Business Meeting
Thursday, March 06
09.15 - 10.15
10.15 - 10.45
Coffee break
10.45 - 12.05
Miscellaneous graph algorithms
Chair: Edward Hirsch
Logic
Chair: Navid Talebanfard
Faster Edge Coloring by Partition Sieving
Modal Separation of Fixpoint Formulae
Listing spanning trees of outerplanar graphs by pivot exchanges
A Dichotomy Theorem for Ordinal Ranks in MSO
Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
Structure-Guided Automated Reasoning
Colorful Vertex Recoloring of Bipartite Graphs
CMSO-transducing tree-like graph decompositions
12.05 - 13.30
Lunch break
13.30 - 15.10
Complexity I
Chair: Heribert Vollmer
Online, streaming, and low-space algorithms
Chair: Thomas Schwentick
The hardness of decision tree complexity (online)
Online Matching with Delays and Size-based Costs
Local Enumeration: The Not-All-Equal Case
Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay
Modular Counting CSP: Reductions and Algorithms
Online Disjoint Set Covers: Randomization is not Necessary
On Average Baby PIH and Its Applications
Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
On read-k projections of the determinant
Two-Dimensional Longest Common Extension Queries in Compact Space
15.10 - 15.40
Coffee break
15.40 - 17.20
Complexity II
Chair: Till Tantau
Exploration and random graphs
Chair: Jacobo Toran
Local equivalence of stabilizer states: a graphical characterisation
Unfairly Splitting Separable Necklaces
Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer
Noisy (binary) searching: simple, fast and correct
Generalized Inner Product Estimation with Limited Quantum Communication
Designing Exploration Contracts
Violating Constant Degree Hypothesis Requires Breaking Symmetry
Canonical labeling of sparse random graphs
Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring
19.00 - 23.00
Conference Dinner (Volksbad)
Friday, March 07
09.15 - 10.15
10.15 - 10.45
Coffee break
10.45 - 12.15
Graphs with structure
Chair: Dominik Scheder
Clustering
Chair: Rüdiger Reischuk
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs (online)
A Faster Algorithm for Constrained Correlation Clustering
Forbidden Patterns in Mixed Linear Layouts
Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
Results on H-freeness testing in graphs of bounded r-admissibility
Approximate Minimum Tree Cover in All Symmetric Monotone Norms Simultaneously
Twin-width one
Cluster Editing on Cographs and Related Classes