| Session 1A, Tuesday 14:00 – 15:00 |
Efficient algorithms and data structures |
| Joshua A. Grochow, Youming Qiao, and Gang Tang |
Average-case algorithms for testing isomorphism of polynomials, algebras, and multilinear forms |
| Ce Jin, Jelani Nelson, and Kewen Wu |
An Improved Sketching Algorithm for Edit Distance |
| Jacob Holm and Eva Rotenberg |
Good r-divisions Imply Optimal Amortized Decremental Biconnectivity |
| Pedro Paredes |
Spectrum preserving short cycle removal on regular graphs |
| Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin |
Distance Computations in the Hybrid Network Model via Oracle Simulations |
| Session 1B, Tuesday 14:00 – 15:00 |
Automata |
| Olga Martynova and Alexander Okhotin |
Lower bounds for graph-walking automata |
| Léo Exibard, Emmanuel Filiot, and Ayrat Khalimov |
Church Synthesis on Register Automata over Linearly Ordered Data Domains |
| Corentin Barloy and Lorenzo Clemente |
Bidimensional Linear Recursive Sequences and Universality of Unambiguous Register Automata |
| Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła |
Synchronizing Strongly Connected Partial DFAs |
| Florent Koechlin and Pablo Rotondo |
Absorbing patterns in BST-like expression-trees |
| Session 2, Tuesday 15:15 – 16:15 |
Invited Talk |
| Peter Bürgisser |
Optimization, Complexity and Invariant Theory |
| Session 3A, Tuesday 16:45– 17:35 |
Quantum (and a random outlier) |
| Ramgopal Venkateswaran and Ryan O’Donnell |
Quantum Approximate Counting with Nonadaptive Grover Iterations |
| Harry Buhrman, Subhasree Patro, and Florian Speelman |
A Framework of Quantum Strong Exponential-Time Hypotheses |
| Simon Apers, András Gilyén, and Stacey Jeffery |
A Unified Framework of Quantum Walk Search |
| Amin Coja-Oghlan, Max Hahn-Klimroth, Philipp Loick, Noela Müller, Konstantinos Panagiotou, and Matija Pasch |
Inference and mutual information on random factor graphs |
| Session 3B, Tuesday 16:45 – 17:35 |
(Approximation) algorithms |
| Ulrich A. Brodowsky and Stefan Hougardy |
The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem |
| Édouard Bonnet |
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio |
| Meike Neuwohner |
An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs |
| Andreas Björklund |
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs |
| Session 4A, Wednesday 14:00 – 15:00 |
Geometric algorithms and coloring |
| Sujoy Bhore and Csaba D. Tóth |
On Euclidean Steiner 1+ε-Spanners |
| Zhengyang Guo and Yi Li |
Geometric Cover with Outliers Removal |
| Haim Kaplan and Jay Tenenbaum |
Locality Sensitive Hashing for Efficient Similar Polygon Retrieval |
| Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos |
Digraph Coloring and Distance to Acyclicity |
| Lars Jaffke, Paloma T. Lima, and Daniel Lokshtanov |
b-Coloring Parameterized by Clique-Width |
| Session 4B, Wednesday 14:00 – 15:00 |
Complexity |
| Anselm Haak, Arne Meier, Om Prakash, and Raghavendra Rao B. V. |
Parameterised Counting in Logspace |
| Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida |
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP |
| Pavel Dvořák and Michal Koucký |
Barrington Plays Cards: The Complexity of Card-based Protocols |
| Tomohiro Koana, Vincent Froese, and Rolf Niedermeier |
Binary Matrix Completion Under Diameter Constraints |
| Pascal Schweitzer and Constantin Seebach |
Resolution with Symmetry Rule applied to Linear Equations |
| Session 5, Wedndesday 15:15 – 16:15 |
Invited Talk |
| Patrice Ossona de Mendez |
First-order transductions of graphs |
| Session 6A, Wednesday 16:45 – 17:45 |
(Online) algorithms |
| Marcin Bienkowski, Björn Feldkord, and Paweł Schmidt |
A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location |
| Hans-Joachim Böckenhauer, Elisabet Burjons, Juraj Hromkoviç, Henri Lotze, and Peter Rossmanith |
Online Simple Knapsack with Reservation Costs |
| Thomas Erlebach, Michael Hoffmann, and Murilo Santos de Lima |
Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries |
| Timothy M. Chan and Saladi Rahul |
Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points |
| William Lochet, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi |
Exploiting Dense Structures in Parameterized Complexity |
| Session 6B, Wednesday 16:45 – 17:45 |
CSPs & Dichotomies |
| Marta Piecyk and Paweł Rzążewski |
Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth |
| Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, and Yixin Shen |
Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding |
| Libor Barto, Diego Battistelli, and Kevin M. Berg |
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case |
| Silvia Butti and Victor Dalmau |
The Complexity of the Distributed Constraint Satisfaction Problem |
| Karolina Okrasa and Paweł Rzążewski |
Complexity of the list homomorphism problem in hereditary graph classes |
| Session 7A, Thursday 14:00 – 15:00 |
Automata and Groups |
| Stefan Göller and Mathieu Hilaire |
Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete |
| Ismaël Jecker |
A Ramsey Theorem for Finite Monoids |
| Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier |
Rice-like theorems for automata networks |
| Markus Lohrey |
Subgroup Membership in GL(2,Z) |
| Pascal Bergsträßer, Moses Ganardi, and Georg Zetzsche |
A characterization of wreath products where knapsack is decidable |
| Session 7B, Thursday 14:00 – 15:00 |
Optimization and Game Theory |
| John Fearnley and Rahul Savani |
A faster algorithm for finding Tarski fixed points |
| Jugal Garg, Edin Husić, and László A. Végh |
Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications |
| Siddharth Barman, Omar Fawzi, and Paul Fermé |
Tight Approximation Guarantees for Concave Coverage Problems |
| Anna Arutyunova and Melanie Schmidt |
Achieving Anonymity via Weak Lower Bound Constraints for k-Median and k-Means |
| Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh |
Diverse Collections in Matroids and Graphs |
| Session 8, Thursday 15:15 – 16:15 |
Invited Talk |
| Lidia Tendera |
On the fluted fragment |
| Session 9A, Thursday 16:45 – 17:35 |
(Parameterised) Algorithms and Complexity |
| Shaohua Li, Marcin Pilipczuk, and Manuel Sorge |
Cluster Editing parameterized above modification-disjoint P_3-packings |
| Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh |
An FPT Algorithm for Elimination Distance to Bounded Degree Graphs |
| Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le |
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration |
| Md Lutfar Rahman and Thomas Watson |
6-Uniform Maker-Breaker Game Is PSPACE-Complete |
| Session 9B, Thursday 16:45 – 17:35 |
Algorithms on Words |
| Paweł Gawrychowski, Maria Kosche, Tore Koß , Florin Manea, and Stefan Siemer |
Efficiently Testing Simon’s Congruence |
| Daniel Gibney and Sharma V. Thankachan |
Finding an Optimal Alphabet Ordering for Lyndon Factorization is Hard |
| Joel D. Day, Pamela Fleischmann, Maria Kosche, Tore Koß, Florin Manea, and Stefan Siemer |
The Edit Distance to k-Subsequence Universality |
| Robert Ferens and Artur Jeż |
Solving one variable word equations in the free group in cubic time |
