Accepted Papers
Track A: Algorithm Design, Data Structures, and Complexity
- A 13/6-Approximation for Strip Packing via the Bottom-Left Algorithm Stefan Hougardy and Bart Zondervan
- Structural Parameterization of Steiner Tree Packing Niko Hastrich and Kirill Simonov
- Optimal Average Disk-Inspection via Fermat’s Principle Konstantinos Georgiou
- A Practical 73/50 Approximation for Contiguous Monotone Moldable Job Scheduling Klaus Jansen and Felix Ohnesorge
- To Buy or Not to Buy: Online Rent-or-Buy on Node-Weighted Graphs Sander Borst and Moritz Venzin
- Maker-Maker games of rank 4 are PSPACE-complete Florian Galliot and Jonas Sénizergues
- Smaller Circuits for Bit Addition Mikhail Goncharov and Alexander Kulikov and Georgii Levtsov
- Broadcast in Almost Mixing Time Anton Paramonov and Roger Wattenhofer
- Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach Antoine Joux and Karol Węgrzycki
- A polynomial bound on the pathwidth of graphs edge-coverable by k shortest paths Julien Baste and Lucas De Meyer and Ugo Giocanti and Etienne Objois and Timothé Picavet
- Counting Unit Circular Arc Intersections Haitao Wang
- Modularity of preferential attachment graphs Katarzyna Rybarczyk and Małgorzata Sulkowska
- A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs Thekla Hamm and Sukanya Pandey and Krisztina Szilagyi
- Higher Hardness Results for the Reconfiguration of Odd Matchings Joseph Dorfer
- Computational hardness of estimating quantum entropies via binary entropy bounds Yupan Liu
- Line Cover and Related Problems Matthias Bentert and Fedor V. Fomin and Petr Golovach and Souvik Saha and Sanjay Seetharaman and Anannya Upasana
- Maximum Reachability Orientation of Mixed Graphs Florian Hörsch
- Threshold-Driven Streaming Graph: Expansion and Rumor Spreading Flora Angileri and Andrea Clementi and Emanuele Natale and Michele Salvi and Isabella Ziccardi
- Stealing From the Dragon's Hoard: Online Unbounded Knapsack With Removal Matthias Gehnen and Moritz Stocker
- The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs Zylan Benjert and Kostas Lakis and Johannes Lengler and Raghu Raman Ravi
- Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More Mihail Stoian
- Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors Roohani Sharma and Michał Włodarczyk
- A linear kernel for Independent Set Reconfiguration in Planar Graphs Nicolas Bousquet and Daniel Cranston
- Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path Metrics Justine Cauvi and Nils Morawietz and Laurent Viennot
- Circle graphs can be recognized in linear time Christophe Paul and Ignaz Rutter
- Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Nikolai Chukhin and Alexander Kulikov and Ivan Mihajlin and Arina Smirnova
- Approximation algorithms for integer programming with resource augmentation Hauke Brinkop and Hua Chen and Lin Chen and Klaus Jansen and Guochuan Zhang
- Kernelization dichotomies for hitting minors under structural parameterizations Marin Bougeret and Eric Brandwein and Ignasi Sau
- The communication complexity of combinatorial auctions in graphs George Christodoulou and Elias Koutsoupias and Annamaria Kovacs and Ioannis Vlachos
- Computing Tarski Fixed Points in Financial Networks Leander Besting and Martin Hoefer and Lars Huth
- Computing Twin-Width via Treedepth and Vertex Integrity Robert Ganian and Mathis Rocton
- Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density Tom-Lukas Breitkopf and André Nichterlein and Vincent Froese and Anton Herrmann and Matthias Bentert
- Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid Haya Diwan and Lisa Hellerstein and Nicole Megow and Jens Schlöter
- Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean functions Manmatha Roy and Swarnalipa Datta and Manaswi Paraashar and Arijit Ghosh and Chandrima Kayal
- Approximate Cartesian Tree Matching with Substitutions Panagiotis Charalampopoulos and Jonas Ellert and Manal Mohamed
- Fully Dynamic Spectral Sparsification for Directed Hypergraphs Sebastian Forster and Gramoz Goranci and Ali Momeni
- Planting and MCMC Sampling from the Potts model Andreas Galanis and Leslie Ann Goldberg and Paulina Smolarova
- Unit Interval Selection in Random Order Streams Cezar-Mihail Alexandru and Adithya Diddapur and Magnús M. Halldórsson and Christian Konrad and Kheeran Naidu
- Time-Optimal Construction of String Synchronizing Sets Jonas Ellert and Tomasz Kociumaka
- A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP Andreas Kalavas and Charalampos Platanos and Thanos Tolias
- List coloring ordered graphs with forbidden induced subgraphs Marta Piecyk and Paweł Rzążewski
- On the Hardness of the One-Sided Code Sparsifier Problem Elena Grigorescu and Alice Moayyedi
- Dynamic Pattern Matching with Wildcards Arshia Ataee Naeini and Amir-Parsa Mobed and Masoud Seddighin and Saeed Seddighin
- 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs Rohit Gurjar and Kilian Rothmund and Thomas Thierauf
- Upper and Lower Bounds for the Linear Ordering Principle Edward Hirsch and Ilya Volkovich
- Optimal Deterministic Rendezvous in Labeled Lines Yann Bourreau and Ananth Narayanan and Alexandre Nolin
- Simple Circuit Extensions for XOR in PTIME Marco Carmosino and Ngu Dang and Tim Jackman
- Modular Counting over 3-Element and Conservative Domains Andrei Bulatov and Amirhossein Kazeminia
- Relative Compressed Reverse Suffix Array Sharma Thankachan and Rahul Shah and M. Oguzhan Kulekci and Mano Prakash Parthasarathi
- Testing H-freeness on sparse graphs, the case of bounded expansion Samuel Humeau and Mamadou Kanté and Daniel Mock and Timothé Picavet and Alexandre Vigny
- Colouring Probe H-Free Graphs Daniel Paulusma and Johannes Rauch and Erik Jan van Leeuwen
- Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms Antonios Antoniadis and Denise Graafsma and Ruben Hoeksma and Maria Vlasiou
- A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity Pavel Dvořák and Bruno Loff and Suhail Sherif
- Lower bounds for ranking-based pivot rules Yann Disser and Georg Loho and Matthew Maat and Nils Mosis
- A Permanental analog of Rank-Nullity Theorem for1 Symmetric Matrices Surabhi Chakrabartty and Priyanshu Kumar Pant and Ranveer Singh
- When is local search both effective and efficient? Artem Kaznatcheev and Sofia Vazquez Alferez
- The Complexity of Homomorphism Reconstruction Revisited Timo Gervens and Martin Grohe and Louis Härtel and Philipp da Silva Fonseca
- Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time Etienne Objois and Adrian Vladu
Track B: Automata, Logic, Semantics and Theory of Programming
- On Effective Banach-Mazur Games and an application to the Poincaré Recurrence Theorem for Category Prajval Koul and Satyadev Nandakumar
- A pumping-like lemma for languages over infinite alphabets Yoav Danieli
- Decidability of Extensions of Presburger Arithmetic by Hardy Field Functions Hera Brown and Jakub Konieczny
- On the complexity of computing Strahler numbers Moses Ganardi and Markus Lohrey
- Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing Marek Černý and Tim Seppelt
- Generalised Quantifiers Based on Rabin-Mostowski Index Denis Kuperberg and Damian Niwinski and Paweł Parys and Michał Skrzypczak
- The Complexity of Resilience for Digraph Queries Manuel Bodirsky and Žaneta Semanišinová
- On the Complexity of Language Membership for Probabilistic Words Antoine Amarilli and Mikaël Monet and Paul Raphaël and Sylvain Salvati
- The asymptotic size of finite irreducible semigroups of rational matrices Stefan Kiefer and Andrew Ryzhikov
- On the p-adic Skolem Problem Piotr Bacik and Joël Ouaknine and David Purser and James Worrell
- One-clock synthesis problems Sławomir Lasota and Mathieu Lehaut and Julie Parreaux and Radosław Piórkowski
- Demystifying Codensity Monads via Duality Fabian Lenke and Stefan Milius and Henning Urbat and Nico Wittrock
- Algorithm and Strategy Construction for Sure-Almost-Sure Stochastic Parity Games Laurent Doyen and Shibashis Guha
- An Improved Version of Hmelevskii's Theorem on Three-Variable Word Equations Aleksi Saarela
- Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata Filip Mazowiecki and Antoni Puch and Daniel Smertnig
- Effective Versions of Strong Measure Zero Matt Rayman
- Guarded Logic and Random Models Oskar Fiuk
- Algebraic characterizations of classes of regular languages in DynFO Corentin Barloy and Felix Tschirbs and Nils Vortmeier and Thomas Zeume
- Efficient Compression in Semigroups Alexander Thumm and Armin Weiß
- Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata Bruno Guillon and Luca Prigioniero and Javad Taheri