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