Monday, March 9
-
13:30–14:00:
Welcome Coffee
-
14:00–14:40:
Tutorial:
Regular languages recognition in restricted models of computation (part 1),
Tatiana Starikovskaya
-
14:40–14:45:
Break
-
14:45–15:25:
Tutorial:
Regular languages recognition in restricted models of computation (part 2),
Gabriel Bathie
-
15:25–15:30:
Break
-
15:30–16:10:
Tutorial:
Regular languages recognition in restricted models of computation (part 3),
Tatiana Starikovskaya
-
16:10–16:30:
Discussions
Tuesday, March 10
-
09:15–10:10:
Welcome Coffee
-
10:10–10:30:
Opening
-
10:30–12:10:
Parallel sessions
-
[A] Approximation Algorithms
- 10:30:
A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm,
Stefan Hougardy and Bart Zondervan
- 10:50:
A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling,
Klaus Jansen and Felix Ohnesorge
- 11:10:
Approximation algorithms for integer programming with resource augmentation,
Hauke Brinkop and Hua Chen and Lin Chen and Klaus Jansen and Guochuan Zhang
- 11:30:
Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time,
Etienne Objois and Adrian Vladu
- 11:50:
Approximate Cartesian Tree Matching with Substitutions,
Panagiotis Charalampopoulos and Jonas Ellert and Manal Mohamed
-
[B] Complexity and Algorithmic Aspects
- 10:30:
The Complexity of Resilience for Digraph Queries,
Manuel Bodirsky and Žaneta Semanišinová
- 10:50:
On the complexity of computing Strahler numbers,
Moses Ganardi and Markus Lohrey
- 11:10:
On the Complexity of Language Membership for Probabilistic Words,
Antoine Amarilli and Mikaël Monet and Paul Raphaël and Sylvain Salvati
- 11:30:
Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing,
Marek Černý and Tim Seppelt
- 11:50:
Efficient Compression in Semigroups,
Alexander Thumm and Armin Weiß
-
12:20–14:00:
Lunch & Discussions
-
14:00–15:40:
Parallel sessions
-
[A] Dynamic/Streaming Algorithms
- 14:00:
Fully Dynamic Spectral Sparsification for Directed Hypergraphs,
Sebastian Forster and Gramoz Goranci and Ali Momeni
- 14:20:
Dynamic Pattern Matching with Wildcards,
Arshia Ataee Naeini and Amir-Parsa Mobed and Masoud Seddighin and Saeed Seddighin
- 14:40:
Unit Interval Selection in Random Order Streams,
Cezar-Mihail Alexandru and Adithya Diddapur and Magnús M. Halldórsson and Christian Konrad and Kheeran Naidu
- 15:00:
Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics,
Justine Cauvi and Nils Morawietz and Laurent Viennot
- 15:20:
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading,
Flora Angileri and Andrea Clementi and Emanuele Natale and Michele Salvi and Isabella Ziccardi
-
[A] Complexity #1
- 14:00:
The Complexity of Homomorphism Reconstruction Revisited,
Timo Gervens and Martin Grohe and Louis Härtel and Philipp da Silva Fonseca
- 14:20:
2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs,
Rohit Gurjar and Kilian Rothmund and Thomas Thierauf
- 14:40:
Maker-Maker games of rank 4 are PSPACE-complete,
Florian Galliot and Jonas Sénizergues
- 15:00:
Higher Hardness Results for the Reconfiguration of Odd Matchings,
Joseph Dorfer
- 15:20:
On the Hardness of the One-Sided Code Sparsifier Problem,
Elena Grigorescu and Alice Moayyedi
-
15:45–16:15:
Coffee Break
-
16:15–17:55:
Parallel sessions
-
[A] Parameterization & Kernels
- 16:15:
Structural Parameterization of Steiner Tree Packing,
Niko Hastrich and Kirill Simonov
- 16:35:
Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More,
Mihail Stoian
- 16:55:
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs,
Thekla Hamm and Sukanya Pandey and Krisztina Szilagyi
- 17:15:
A linear kernel for Independent Set Reconfiguration in Planar Graphs,
Nicolas Bousquet and Daniel Cranston
- 17:35:
Kernelization dichotomies for hitting minors under structural parameterizations,
Marin Bougeret and Eric Brandwein and Ignasi Sau
-
[A] Testing & Counting
- 16:15:
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean functions,
Manmatha Roy and Swarnalipa Datta and Manaswi Paraashar and Arijit Ghosh and Chandrima Kayal
- 16:35:
Counting Unit Circular Arc Intersections,
Haitao Wang
- 16:55:
Modular Counting over 3-Element and Conservative Domains,
Andrei Bulatov and Amirhossein Kazeminia
- 17:15:
A Permanental analog of Rank-Nullity Theorem for1 Symmetric Matrices,
Surabhi Chakrabartty and Priyanshu Kumar Pant and Ranveer Singh
- 17:35:
Testing H-freeness on sparse graphs, the case of bounded expansion,
Samuel Humeau and Mamadou Kanté and Daniel Mock and Timothé Picavet and Alexandre Vigny
-
18:00–20:00:
Reception
Wednesday, March 11
-
09:00–10:00:
Invited Talk:
Advancements in Online Edge Coloring Algorithms,
Ola Svensson
-
10:00–10:30:
Coffee Break
-
10:30–12:10:
Parallel sessions
-
[A] Random Structures
- 10:30:
Planting and MCMC Sampling from the Potts model,
Andreas Galanis and Leslie Ann Goldberg and Paulina Smolarova
- 10:50:
The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs,
Zylan Benjert and Kostas Lakis and Johannes Lengler and Raghu Raman Ravi
- 11:10:
Broadcast in Almost Mixing Time,
Anton Paramonov and Roger Wattenhofer
- 11:30:
Modularity of preferential attachment graphs,
Katarzyna Rybarczyk and Małgorzata Sulkowska
- 11:50:
Computational hardness of estimating quantum entropies via binary entropy bounds,
Yupan Liu
-
[B] Computability & Logic
- 10:30:
Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions,
Hera Brown and Jakub Konieczny
- 10:50:
Effective Versions of Strong Measure Zero,
Matt Rayman
- 11:10:
Generalised Quantifiers Based on Rabin-Mostowski Index,
Denis Kuperberg and Damian Niwinski and Paweł Parys and Michał Skrzypczak
- 11:30:
On the p-adic Skolem Problem,
Piotr Bacik and Joël Ouaknine and David Purser and James Worrell
- 11:50:
The asymptotic size of finite irreducible semigroups of rational matrices,
Stefan Kiefer and Andrew Ryzhikov
-
12:20–14:00:
Lunch & Discussions
-
14:00–15:40:
Parallel sessions
-
[A] Algorithm Analysis
- 14:00:
Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach,
Antoine Joux and Karol Węgrzycki
- 14:20:
Lower bounds for ranking-based pivot rules,
Yann Disser and Georg Loho and Matthew Maat and Nils Mosis
- 14:40:
When is local search both effective and efficient?,
Artem Kaznatcheev and Sofia Vazquez Alferez
- 15:00:
Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms,
Antonios Antoniadis and Denise Graafsma and Ruben Hoeksma and Maria Vlasiou
- 15:20:
Optimal Average Disk-Inspection via Fermat’s Principle,
Konstantinos Georgiou
-
[B] Games & Automata
- 14:00:
One-clock synthesis problems,
Sławomir Lasota and Mathieu Lehaut and Julie Parreaux and Radosław Piórkowski
- 14:20:
A pumping-like lemma for languages over infinite alphabets,
Yoav Danieli
- 14:40:
Algorithm and Strategy Construction for Sure-Almost-Sure Stochastic Parity Games,
Laurent Doyen and Shibashis Guha
- 15:00:
Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata,
Filip Mazowiecki and Antoni Puch and Daniel Smertnig
- 15:20:
Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata,
Bruno Guillon and Luca Prigioniero and Javad Taheri
-
15:45–16:15:
Coffee Break
-
16:15–17:55:
Parallel sessions
-
[A] Graph parameters
- 16:15:
A polynomial bound on the pathwidth of graphs edge-coverable by k shortest paths,
Julien Baste and Lucas De Meyer and Ugo Giocanti and Etienne Objois and Timothé Picavet
- 16:35:
Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors,
Roohani Sharma and Michał Włodarczyk
- 16:55:
Computing Twin-Width via Treedepth and Vertex Integrity,
Robert Ganian and Mathis Rocton
- 17:15:
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density,
Tom-Lukas Breitkopf and André Nichterlein and Vincent Froese and Anton Herrmann and Matthias Bentert
- 17:35:
Colouring Probe H-Free Graphs,
Daniel Paulusma and Johannes Rauch and Erik Jan van Leeuwen
-
[A] Complexity #2
- 16:15:
Smaller Circuits for Bit Addition,
Mikhail Goncharov and Alexander Kulikov and Georgii Levtsov
- 16:35:
Simple Circuit Extensions for XOR in PTIME,
Marco Carmosino and Ngu Dang and Tim Jackman
- 16:55:
Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank,
Nikolai Chukhin and Alexander Kulikov and Ivan Mihajlin and Arina Smirnova
- 17:15:
Upper and Lower Bounds for the Linear Ordering Principle,
Edward Hirsch and Ilya Volkovich
- 17:35:
A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity,
Pavel Dvořák and Bruno Loff and Suhail Sherif
-
18:00–19:00:
Business Meeting
Thursday, March 12
-
09:00–10:00:
Invited Talk:
Moments in Time: Algebraic Analysis for Solvable Loops,
Laura Kovacs
-
10:00–10:30:
Coffee Break
-
10:30–11:50:
Parallel sessions
-
[A] Online/Dynamic Algorithms
- 10:30:
To Buy or Not to Buy: Online Rent-or-Buy on Node-Weighted Graphs,
Sander Borst and Moritz Venzin
- 10:50:
Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal,
Matthias Gehnen and Moritz Stocker
- 11:10:
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid,
Haya Diwan and Lisa Hellerstein and Nicole Megow and Jens Schlöter
- 11:30:
A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP,
Andreas Kalavas and Charalampos Platanos and Thanos Tolias
-
[A] Games & Strings
- 10:30:
Computing Tarski Fixed Points in Financial Networks,
Leander Besting and Martin Hoefer and Lars Huth
- 10:50:
The communication complexity of combinatorial auctions in graphs,
George Christodoulou and Elias Koutsoupias and Annamaria Kovacs and Ioannis Vlachos
- 11:10:
Time-Optimal Construction of String Synchronizing Sets,
Jonas Ellert and Tomasz Kociumaka
- 11:30:
Relative Compressed Reverse Suffix Array,
Sharma Thankachan and Rahul Shah and M. Oguzhan Kulekci and Mano Prakash Parthasarathi
-
12:00–13:00:
Lunch
-
13:10:
Bus departure for snowshoe outing
-
17:30–18:00:
(estimated) Return to Grenoble
-
19:30:
Conference Dinner
Friday, March 13
-
09:00–10:00:
Invited Talk:
Query Languages for Machine-Learning Models,
Martin Grohe
-
10:00–10:30:
Coffee Break
-
10:30–12:10:
Parallel sessions
-
[A] Graphs & Algorithms
- 10:30:
Circle graphs can be recognized in linear time,
Christophe Paul and Ignaz Rutter
- 10:50:
List coloring ordered graphs with forbidden induced subgraphs,
Marta Piecyk and Paweł Rzążewski
- 11:10:
Optimal Deterministic Rendezvous in Labeled Lines,
Yann Bourreau and Ananth Narayanan and Alexandre Nolin
- 11:30:
Line Cover and Related Problems,
Matthias Bentert and Fedor V. Fomin and Petr Golovach and Souvik Saha and Sanjay Seetharaman and Anannya Upasana
- 11:50:
Maximum Reachability Orientation of Mixed Graphs,
Florian Hörsch
-
[B] Logic & Language Theory
- 10:30:
Demystifying Codensity Monads via Duality,
Fabian Lenke and Stefan Milius and Henning Urbat and Nico Wittrock
- 10:50:
Guarded Logic and Random Models,
Oskar Fiuk
- 11:10:
On Effective Banach-Mazur Games and an application to the Poincaré Recurrence Theorem for Category,
Prajval Koul and Satyadev Nandakumar
- 11:30:
An Improved Version of Hmelevskii's Theorem on Three-Variable Word Equations,
Aleksi Saarela
- 11:50:
Algebraic characterizations of classes of regular languages in DynFO,
Corentin Barloy and Felix Tschirbs and Nils Vortmeier and Thomas Zeume
-
12:20–14:00:
Lunch & Discussions