Session 1A, Tuesday 14:00 – 15:00 
Efficient algorithms and data structures 

Joshua A. Grochow, Youming Qiao, and Gang Tang 
Averagecase 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 rdivisions Imply Optimal Amortized Decremental Biconnectivity 

Pedro Paredes 
Spectrum preserving short cycle removal on regular graphs 

Keren CensorHillel, 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 graphwalking 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 BSTlike expressiontrees 

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 ExponentialTime Hypotheses 

Simon Apers, András Gilyén, and Stacey Jeffery 
A Unified Framework of Quantum Walk Search 

Amin CojaOghlan, Max HahnKlimroth, 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 2Opt Heuristic for the Euclidean Traveling Salesman Problem 

Édouard Bonnet 
Inapproximability of Diameter in superlinear time: Beyond the 5/3 ratio 

Meike Neuwohner 
An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in dClaw Free Graphs 

Andreas Björklund 
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs 

Tuesday 17:35 – 
Social Event 

Party on gather.town 


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 
bColoring Parameterized by CliqueWidth 

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 
OneTape Turing Machine and Branching Program Lower Bounds for MCSP 

Pavel Dvořák and Michal Koucký 
Barrington Plays Cards: The Complexity of Cardbased 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 
Firstorder 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 NonMetric Facility Location 

HansJoachim 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 
RoundCompetitive Algorithms for Uncertainty Problems with Parallel Queries 

Timothy M. Chan and Saladi Rahul 
Simple MultiPass 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 
Finegrained 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 twoparametric timed automata with one parameter is EXPSPACEcomplete 

Ismaël Jecker 
A Ramsey Theorem for Finite Monoids 

Guilhem Gamard, Pierre Guillon, Kevin Perrot, and Guillaume Theyssier 
Ricelike 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 kMedian and kMeans 

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 modificationdisjoint P_3packings 

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 
6Uniform MakerBreaker Game Is PSPACEComplete 

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 kSubsequence Universality 

Robert Ferens and Artur Jeż 
Solving one variable word equations in the free group in cubic time 
