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