Programme

 

All times are CET!

 

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