Program

All times are UTC+1, i.e., the timezone of Marseille, France.

Tuesday 15 March

Session 1: 10:00 - 12:00

Session 1a (chair: Petra Berenbrink): circuits, complexity and codes (2h)

• Carla Groenland, Isja Mannens, Jesper Nederlof and Krisztina Szilágyi: Tight bounds for counting colorings and connected edge sets parameterized by cutwidth (teaser, article)
• Pawel Idziak, Piotr Kawałek and Jacek Krzaczkowski: Satisfiability of circuits and equations over finite Malcev algebras (article)
• Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu and Saket Saurabh: Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems (article)
• Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh and Gopinath Mishra: Faster Counting and Sampling Algorithms using Colorful Decision Oracle (teaser, article)

Session 1b (chair: Nathalie Aubrun): tiling and probabilities (2h)

• Antonin Callard and Benjamin Hellouin de Menibus: The aperiodic Domino problem in higher dimension (teaser, article)
• Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki and Guillaume Theyssier: Oritatami systems assemble shapes no less complex than tile assembly model (aTAM) (teaser, article)
• Laurent Bienvenu, Valentino Delle Rose and Tomasz Steifer: Probabilistic vs deterministic gamblers (article)
• Christopher Williamson: Sharp indistinguishability bounds from non-uniform approximations (article)

Tutorial (chair: Sylvain Schmitz): 14:00 - 15:00
Amina Doumane, Regular expressions for graphs of tree-width 2

Session 2: 15:30 - 17:00

Session 2a (chair: Eric Allender): circuits, codes (1h30)

• Hanlin Ren and Rahul Santhanam: A Relativization Perspective on Meta-Complexity (teaser, article)
• Petr Gregor, Torsten Mütze and Arturo Merino: Star transposition Gray codes for multiset permutations (article)
• Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee and Jin Young Son: On Explicit Constructions of Extremely Depth Robust Graphs (teaser, article)

Session 2b (chair: Jeffrey Shallit): geometry (1h30)

• Jianer Chen, Qin Huang, Iyad Kanj and Ge Xia: Near-Optimal Algorithms for Point-Line Covering Problems (article)
• Jack H. Lutz, Neil Lutz and Elvira Mayordomo: Extending the Reach of the Point-to-Set Principle (article)
• Donald Stull: Optimal Oracles for Point-to-Set Principles (article)

Wednesday 16 March

Session 3: 10:00 - 12:00

Session 3a (chair: Arne Meier): complexity (2h)

• Michael Lampis: Determining a Slater Winner is Complete for Parallel Access to NP (article)
• C Ramya and Anamay Tengse: On finer separations between subclasses of Read-once Oblivious ABPs (article)
• Martin Skoviera and Peter Varsa: NP-completeness of perfect matching index of cubic graphs (teaser, article)
• Mrinal Kumar, C. Ramya, Ramprasad Saptharishi and Anamay Tengse: If VNP is hard, then so are equations for it (article)

Session 3b (chair: Benjamin Monmege): matrices, networks and scheduling (2h)

• Yung-Chung Chiu and Hsueh-I Lu: Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths (article)
• Yacine Al Najjar, Walid Ben-Ameur and Jérémie Leguay: Approximability of Robust Network Design: the Directed Case (article)
• Michał Pilipczuk, Marek Sokołowski and Anna Zych-Pawlewicz: Compact representation for matrices of bounded twin-width (article)
• Hiromichi Goko, Akitoshi Kawamura, Yasushi Kawase, Kazuhisa Makino and Hanna Sumita: Online Scheduling on Identical Machines with a Metric State Space (article)

Invited talk 1 (chair: Cyril Nicaud): 14:00 - 15:00
Marie Albenque, Local limit of random discrete surface with (or without!) a statistical physics model

Session 4: 15:30 - 17:30

Session 4a (chair: Massimo Lauria): circuits, complexity and groups (2h)

• András Z. Salamon and Michael Wehar: Superlinear Lower Bounds Based on ETH (teaser, article)
• Stefan Dantchev, Nicola Galesi, Abdul Ghani and Barnaby Martin: Depth lower bounds in Stabbing Planes for combinatorial principles (article)
• Nikolay Bazhenov, Dariusz Kalociński and Michał Wrocławski: Intrinsic complexity of recursive functions on natural numbers with standard order (article)
• Andrei Bulatov and Akbar Rafiey: The Ideal Membership Problem and Abelian Groups (article)

Session 4b (chair: Ioan Todinca): graphs (1h30)

• Jesper Nederlof, Michał Pilipczuk, Céline Swennenhuis and Karol Węgrzycki: Isolation schemes for problems on decomposable graphs (teaser, article, longer video)
• Pierre Bergé, Guillaume Ducoffe and Michel Habib: Subquadratic-time algorithm for the diameter and all eccentricities on median graphs (article)
• Fedor Fomin, Petr Golovach, William Lochet, Danil Sagunov, Saket Saurabh and Kirill Simonov: Detours in Directed Graphs (teaser, article)

Thursday 17 March

Session 5: 10:00 - 12:00

Session 5a (chair: Karoliina Lehtinen): games and verification (2h)

• Patricia Bouyer, Mickael Randour and Pierre Vandenhove: Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs (teaser, article)
• Alexander Kozachinskiy: One-to-Two-Player Lifting for Mildly Growing Memory (article)
• Sławomir Lasota: Improved Ackermannian lower bound for the Petri nets reachability problem (article)
• S. Akshay, Hugo Bazille, Blaise Genest and Mihir Vahanwala: On Robustness for the Skolem and positivity problems (teaser, article)

Session 5b (chair: Akanksha Agrawal): optimisation (1h30)

• Hiromichi Goko, Kazuhisa Makino, Shuichi Miyazaki and Yu Yokoi: Maximally Satisfying Lower Quotas in the Hospitals/Residents Problem with Ties (article)
• Tomohiro Koana, Christian Komusiewicz, André Nichterlein and Frank Sommer: Covering Many (or Few) Edges with k Vertices in Sparse Graphs (teaser, article)
• Telikepalli Kavitha: Fairly Popular Matchings and Optimality (teaser, article)

Invited talk 2 (chair: Petra Berenbrink): 14:00 - 15:00
Maria-Florina Balcan, Generalization Guarantees for Data-driven Mechanism Design

Session 6: 15:30 - 17:30

Session 6a (chair: Benjamin Monmege): network, scheduling and optimisation (2h)

• Ramtin Afshar, Michael T. Goodrich, Pedro Matias and Martha C. Osegueda: Mapping Networks via Parallel kth-Hop Traceroute Queries (teaser, article)
• Quanquan C. Liu, Manish Purohit, Zoya Svitkina, Erik Vee and Joshua R. Wang: Scheduling with Communication Delay in Near-Linear Time (teaser, article)
• Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack and Lars Rohwedder: Cardinality Constrained Scheduling in Online Models (article)
• Ahmad Biniaz, Majid Daliri and Amir Hossein Moradpour: A 10-Approximation of the π/2-MST (article)

Session 6b (chair: Yuval Filmus): quantum (2h)

• Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer, Nikhil Mande, Manaswi Paraashar and Ronald de Wolf: Symmetry and Quantum Query-to-Communication Simulation (article)
• Nikhil Mande, Swagato Sanyal and Suhail Sherif: One-Way Communication Complexity and Non-Adaptive Decision Trees (article)
• Xinyu Wu: Analyzing XOR-Forrelation through stochastic calculus (article)
• Sander Gribling and Harold Nieuwboer: Improved quantum lower and upper bounds for matrix scaling (article)

Friday 18 March

Session 7: 10:00 - 11:30

Session 7a (chair: Frank Stephan): groups and geometry (1h30)

• (recorded talk) Takeshi Tokuyama and Ryo Yoshimura: High-Quality Consistent Digital Rays via Vector Field Rounding (teaser, article)
• Bireswar Das, Anant Kumar, Shivdutt Sharma and Dhara Thakkar: Linear Space Data Structures for Finite Groups with Constant Query-time (article)
• Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao and Armin Weiss: The isomorphism problem for plain groups is in ∑_3^P (teaser, article)

Session 7b (chair: Henning Fernau): trees and graphs (1h30)

• Mamadou M. Kanté, Eun Jung Kim, O-Joung Kwon and Sang-il Oum: Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k (teaser, article)
• Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki and Kunihiro Wasa: Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint (teaser, article)
• Lars Jaffke, O-Joung Kwon and Jan Arne Telle: Classes of intersection digraphs with good algorithmic properties (article)

Business meeting: 13:30 - 14:00

Invited talk 3 (chair: Thomas Erlebach): 14:00 - 15:00
Fabian Kuhn, Deterministic Distributed Symmetry Breaking at the Example of Distributed Graph Coloring

Session 8: 15:30 - 17:30

Session 8a (chair: Dietmar Berwanger): logic (1h30)

• Eric Goubault, Jérémy Ledent and Sergio Rajsbaum: A Simplicial Model for KB4: Epistemic Logic with Agents that May Die (teaser, article)
• Pascal Baumann, Moses Ganardi, Ramanathan Thinniyam Srinivasan and Georg Zetzsche: Existential definability over the subword ordering (article)
• Leroy Chew and Friedrich Slivovsky: Towards Uniform Certification in QBF (teaser, article)

Session 8b (chair: Thomas Schwentick): trees and shortest paths (2h)

• Nader Bshouty and Catherine Haddad-Zaknoon: On Testing Decision Tree (article)
• Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci, Guido Proietti and Mirko Rossi: Single-source shortest p-disjoint paths: fast computation and sparse preservers (article)
• Michael Elkin and Ofer Neiman: Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication (article)
• Eugen Füchsle, Hendrik Molter, Rolf Niedermeier and Malte Renken: Delay-Robust Routes in Temporal Graphs (article)