Track A accepted 135 papers out of 445 submissions.
Track B accepted 35 papers out of 118 submissions.
Max Dupre la Tour, Manuel Lafond, Ndiame Ndiaye, and Adrian Vetta.
k-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for k≥5
Kiril Bangachev, S. Matthew Weinberg.
q-Partitioning Valuations: Exploring the Space BetweenSubadditive and Fractionally Subadditive Valuations
Ahmed Shalaby and Damien Woods.
An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
Yu Chen and Zihan Tan.
Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
Andrei Bulatov and Stanislav Zivny.
Satisfiability of commutative vs. non-commutative CSPs
Shaofeng H.-C. Jiang, and Jianing Lou.
Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
Benjamin Bergougnoux, Édouard Bonnet, and Julien Duron.
Mim-Width is paraNP-complete
Karl Bringmann, Nick Fischer, Bernhard Haeupler, and Rustam Latypov.
Near-Optimal Directed Low-Diameter Decompositions
Silvia Butti, Alberto Larrauri, and Stanislav Zivny.
Optimal Inapproximability of Promise Equations over Finite Groups
Sahar Diskin, Ilay Hoshen, and Maksim Zhukovskii.
Tiling Random Regular Graphs Efficiently
Deeksha Adil and Thatchaphol Saranurak.
Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method
Yoann Dieudonné, Arnaud Labourel, and Stéphane Devisme.
Graph Exploration: The Impact of a Distance Constraint
Tamio-Vesa Nakajima and Stanislav Zivny.
Maximum Bipartite vs. Triangle-Free Subgraph
Shuichi Hirahara and Naoto Ohsaka.
Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration
Naoto Ohsaka.
Yet Another Simple Proof of the PCRP Theorem
Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, and Gregory B. Sorkin.
Belief Propagation Guided Decimation on Random k-XORSAT
Junyao Zhao.
Universal Online Contention Resolution with Preselected Order
Lars Rohwedder.
ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines
Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, and Andrea Vattani.
A New Impossibility Result for Online Bipartite Matching Problems
Barış Can Esmer and Ariel Kulik.
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza, and Mario Valencia-Pabon.
Computing Distances on Graph Associahedra is Fixed-parameter Tractable
Ben Young.
The Converse of the Real Orthogonal Holant Theorem
Giordano Giambartolomei, Frederik Mallmann-Trenn, and Raimundo Saona.
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
Nairen Cao, Shi Li, and Jia Ye.
Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang.
New Results on a General Class of Minimum Norm Optimization Problems
Nir Lavee and Gal Beniamini.
Counting Permutation Patterns with Multidimensional Trees
Omri Ben-Eliezer, Tomer Grossman, and Moni Naor.
On the Instance Optimality of Detecting Collisions and Subgraphs
Koustav Bhanja.
Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s,t)-cut
Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, and Oren Weimann.
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
Koppány István Encz, Monaldo Mastrolilli, and Eleonora Vercesi.
Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
Aditya Anand, Euiwoong Lee, Jason Li, and Thatchaphol Saranurak.
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
Andreas Galanis, Leslie Ann Goldberg, and Paulina Smolarova.
Low-temperature Sampling on Sparse Random Graphs
Michael Dinitz, Ama Koranteng, and Yasamin Nazari.
Approximation Algorithms for Optimal Hopsets
Alexandra Lassota and Koen Ligthart.
Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns
Daniel Ye.
Deterministic Independent Sets in the Semi-Streaming Model
Ragesh Jaiswal, Amit Kumar, and Jatin Yadav.
Robust-Sorting and Applications to Ulam-Median
Lvzhou Li and Jingquan Luo.
Nearly Optimal Circuit Size for Sparse Quantum State Preparation
Thomas Schneider and Pascal Schweitzer.
An Upper Bound on the Weisfeiler-Leman Dimension
Antares Chen, Lorenzo Orecchia, and Erasmo Tani.
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game
Dani Dorfman, Haim Kaplan, Uri Zwick, Mikkel Thorup, and Robert Tarjan.
Faster all-pairs optimal electric car routing
Pierre Fraigniaud, Maël Luce, Frédéric Magniez, and Ioan Todinca.
Deterministic Even-Cycle Detection in Broadcast CONGEST
Péter Biró, Gergely Csáji, and Ildikó Schlotter.
Stable Hypergraph Matching in Unimodular Hypergraphs
Karthekeyan Chandrasekaran, Siyue Liu, and R. Ravi.
Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations
Gramoz Goranci, Monika Henzinger, Harald Räcke, and A. R. Sricharan.
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Sanjeev Khanna, Aaron Putterman, and Madhu Sudan.
A Theory of Spectral CSP Sparsification
Gianluca De Marco and Dariusz R. Kowalski.
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
Gramoz Goranci, Adam Karczmarz, Ali Momeni, and Nikos Parotsidis.
Fully Dynamic Algorithms for Transitive Reduction
Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski, and Wen-Horng Sheu.
Faster Semi-streaming Matchings via Alternating Trees
Simon Apers, Minbo Gao, Zhengfeng Ji, and Chenghua Liu.
Quantum Speedup for Sampling Random Spanning Trees
Hendrik Molter, Meirav Zehavi, and Amit Zivan.
Treewidth Parameterized by Feedback Vertex Number
Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto.
Shared Randomness Helps with Local Distributed Problems
Deeksha Adil, Shunhua Jiang, and Rasmus Kyng.
Acceleration Meets Inverse Maintenance: Faster ℓ∞-Regression
Andreas Galanis, Leslie Ann Goldberg, and Xusheng Zhang.
One-Shot Learning for k-SAT
Sanjeev Khanna, Aaron Putterman, and Madhu Sudan.
Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, and Johannes Schmitt.
Parameterised Holant Problems
Kiarash Banihashem, Leyla Biabani, and Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh.
Dynamic Algorithms for Submodular Matching
Roni Con, Zeyu Guo, Ray Li, and Zihan Zhang.
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
Sebastian Haslebacher.
ARRIVAL: Recursive Framework & l1-Contraction
Karthekeyan Chandrasekaran, Chandra Chekuri, and Weihao Zhu.
Online Disjoint Spanning Trees and Polymatroid Bases
Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan.
New Bounds for the Ideal Proof System in Positive Characteristic
Per Austrin, Ioana Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan, and Nutan Limaye.
Algorithms for the Diverse-k-SAT problem: the geometry of satisfying assignments
Daniel Paul-Pena and C. Seshadhri.
Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
Anders Aamand, Allen Liu, and Shyam Narayanan.
Near-Optimal Trace Reconstruction for Mildly Separated Strings
Xi Chen, William Pires, Toniann Pitassi, and Rocco A. Servedio.
Relative-error testing of conjunctions and decision lists
Yuni Iwamasa, Taihei Oki, and Tasuku Soma.
Algorithmic aspects of semistability of quiver representations
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, and Miklos Santha.
On the quantum time complexity of divide and conquer
Arjan Cornelissen, Simon Apers, andSander Gribling.
How to compute the volume in low dimension?
Debajyoti Kar, Arindam Khan, and Malin Rau.
Improved Approximation Algorithms for Three-Dimensional Bin Packing
Amir Carmel, Debarati Das, Evangelos Kipouridis, and Evangelos Pipis.
Fitting Tree Metrics and Ultrametrics in Data Streams
Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi.
(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs
Jingxun Liang andRenfei Zhou.
Optimal Static Fully Indexable Dictionaries
Penghui Yao and Mingnan Zhao.
A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
Pierre Aboulker, Édouard Bonnet, Timothé Picavet, and Nicolas Trotignon.
Induced Disjoint Paths Without an Induced Minor
Sanjeev Khanna, Christian Konrad, and Jacques Dark.
Streaming Maximal Matching with Bounded Deletions
Ishan Bansal, Joe Cheriyan, Sanjeev Khanna, and Miles Simmons.
Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
Sepideh Mahabadi, Mohammad Roghani, and Jakub Tarnawski.
A 0.51-Approximation of Maximum Matching in Sublinear n1.5 Time.
Sándor Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer.
Drainability and Fillability of Polyominoes in Diverse Models of Global Control
Greg Bodwin, Michael Dinitz, Ama Koranteng, and Lily Wang.
Light Edge Fault Tolerant Graph Spanners
Rasmus Kyng, Simon Meierhans, and Gernot Zöcklein.
A Simple Dynamic Spanner via APSP
Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang.
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi, and Sumedha.
On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
Shiri Chechik, Hongyi Chen, and Tianyi Zhang.
Improved Streaming Edge Coloring
Lars Rohwedder and Leander Schnaars.
3.415-Approximation for Coflow Scheduling via Iterated Rounding
Zejia Chen, Yulin Wang, Chihao Zhang, and Zihan Zhang.
Decay of correlation for edge colorings when q > 3 Δ
Evangelos Kosinas. An Optimal 3-Fault-Tolerant Connectivity Oracle
Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong.
Faster Fréchet Distance under Transformations
Time Nathan Claudet and Simon Perdrix. Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial
Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, and Weronika Wrzos-Kaminska.
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
Prem Nigam Kar, David E. Roberson, Tim Seppelt, and Peter Zeman.
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Leah London Arazi and Amir Shpilka.
On the Complexity of Hazard-Free Formulas
Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, and Giannos Stamoulis.
Faster diameter computation in graphs of bounded Euler genus
Shuichi Hirahara and Nobutaka Shimizu.
An Optimal Error-Correcting Reduction for Matrix Multiplication
Paweł Gawrychowski and Wojciech Janczewski.
Optimal Distance Labeling for Permutation Graphs
Boning Meng, Juqiu Wang, and Mingji Xia.
P-time algorithms for typical #EO problems
Martin Costa and Ermiya Farokhnejad.
Deterministic k-Median Clustering in Near-Optimal Time
Karthekeyan Chandrasekaran, Chandra Chekuri, and Shubhang Kulkarni.
On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions
Adi FIne, Haim Kaplan, and Uri Stemmer.
Minimizing Recourse in an Adaptive Balls and Bins Game
Valentin Gledel, Nacim Oijid, Sébastien Tavenas, Stéphan Thomassé.
On the complexity of Client-Waiter and Waiter-Client games
Maxime Flin and Magnús M. Halldórsson.
Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries
Oded Lachish, Felix Reidl, Christine Awofeso, Patrick Greaves, and Amit Levi.
Testing Ck -freeness in Bounded Admissibility Graphs
Tsubasa Harada and Toshiya Itoh.
A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
Guilherme C. M. Gomes, Raul Lopes, and Ignasi Sau.
Revisiting Directed Disjoint Paths on tournaments (and relatives)
Shikha Singh and Aditya Potukuchi.
Unbalanced Random Matching Markets with Partial Preferences
Sujoy Bhore and Lazar Milenković.
Light Spanners with Small Hop-Diameter
Cheng-Hao Fu, Andrea Lincoln, and Rene Reyes.
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders.
Faster, Deterministic and Space Efficient Subtrajectory Clustering
Hessa Al-Thani and Viswanath Nagarajan.
Identifying Approximate Minimizers under Stochastic Uncertainty
Piotr Indyk and Ying Feng.
Even Faster Algorithm for the Chamfer Distance
Mahsa Derakhshan and Mohammad Saneian.
Query Efficient Weighted Stochastic Matching
Jiaqi Cheng and Rishab Goyal.
Boosting SNARKs and Rate-1 Barrier in Arguments of Knowledge
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Pittu, Ali Vakilian, and David Woodruff.
Guessing Efficiently for Constrained Subspace Approximation
Chirag Pabbaraju and Ali Vakilian.
New and Improved Bounds for Markov Paging
Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang.
Weakly Approximating Knapsack in Subquadratic Time
Chris Jones and Lucas Pesenti.
Fourier Analysis of Iterative Algorithms
Agustín Caracci, Christoph Dürr, and José Verschae.
Randomized Binary and Tree Search under Pressure
Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß, and Mirza Redžić.
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
Shucheng Chi, Ran Duan, Benyu Wang, and Tianle Xie.
Undirected 3-Fault Replacement Path in Nearly Cubic Time
Lars Rohwedder, Arman Rouhani, and Leo Wennmann.
Cost Preserving Dependent Rounding for Allocation Problems
Sharma V. Thankachan, Daniel Gibney, Jackson Huffstutler, and Mano Prakash Parthasarathi.
Repetition Aware Text Indexing for Matching Patterns with Wildcards
Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, and Shikha Singh.
Incremental Approximate Single-Source Shortest Paths with Predictions
Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi.
Towards the Proximity Conjecture on Group-Labeled Matroids
Shiyuan Feng, William Swartworth, and David Woodruff.
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
Artur Czumaj, Guichen Gao, Mohsen Ghaffari, and Shaofeng H.-C. Jiang.
Fully Scalable MPC Algorithms for Euclidean k-Center
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue.
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Paul Beame and Michael Whitmeyer.
Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles
Alex Bortolotti, Monaldo Mastrolilli, and Luis Felipe Vargas.
On the Degree Automatability of Sum-of-Squares Proofs
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, and Madhu Sudan.
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
Vishwas Bhargava and Devansh Shringi.
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition
Adam Górkiewicz and Adam Karczmarz.
On Incremental Approximate Shortest Paths in Directed Graphs
Shabarish Chenakkod, Michał Dereziński, and Xiaoyu Dong.
Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
Mahsa Derakhshan, Andisheh Ghasemi, and Rajmohan Rajaraman.
One-way Communication Complexity of Minimum Vertex Cover in General Graphs
Aurelio Sulser and Maximilian Probst Gutenberg.
Near-Optimal Algorithm for Directed Expander Decompositions
Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, and Jay Sethuraman.
Scarf's Algorithm on Arborescence Hypergraphs
Aleksandros Sobczyk.
Deterministic complexity analysis of Hermitian eigenproblems
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond.
Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
Antonio Casares and Pierre Ohlmann.
The memory of ω-regular and BC(Σ02) objectives
Santiago Guzmán Pro and Barnaby Martin.
Restricted CSPs and F-free Digraph Algorithmics
Lukas Fleischer, Florian Stober, Alexander Thumm, and Armin Weiß.
Membership and Conjugacy in Inverse Semigroups
Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, and Stanislav Zivny.
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
Krishnendu Chatterjee, Laurent Doyen, Jean-Francois Raskin, and Ocan Sankur.
The Value Problem for Multiple-Environment MDPs with Parity Objective
Alexey Barsukov, Michael Pinsker, and Jakub Rydval.
Containment for Guarded Monotone Strict NP
Christina Gehnen, Dominique Unruh, and Joost-Pieter Katoen.
Bayesian Inference in Quantum Programs
Karoliina Lehtinen and Nathan Lhote.
A collapse of the parity index hierarchy of tree automata, based on Cantor-Bendixson ranks
Olga Martynova and Alexander Okhotin.
Nondeterministic tree-walking automata are not closed under complementation
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota, and Łukasz Orlikowski.
Reachability in 3-VASS is Elementary
Tikhon Pshenitsyn.
First-Order Intuitionistic Linear Logic and Hypergraph Languages
León Bohn, Yong Li, Christof Löding, and Sven Schewe.
Saturation Problems for Families of Automata
Ruiwen Dong.
Submonoid Membership in n-dimensional lamplighter groups and S-unit equations
Moritz Lichter and Benedikt Pago.
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
Jin-Yi Cai and Jin Soo Ihm.
Holant* Dichotomy on Domain Size 3: A Geometric Perspective
Fugen Hagihara and Akitoshi Kawamura.
The Ultimate Signs of Second-Order Holonomic Sequences
Djamel Eddine Amir and Benjamin Hellouin de Menibus.
Minimality and computability of languages of G-shifts
Michal Ajdarów, James C. A. Main, Petr Novotný, and Mickael Randour.
Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs
Nikolas Mählmann.
Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
Olivier Idir and Karoliina Lehtinen.
Using games and universal trees to characterise the nondeterministic index of tree languages
Spencer Van Koevering, Wojciech Różowski, and Alexandra Silva.
Weighted GKAT: Completeness and Complexity
Philippe Schnoebelen, J. Veron, and Isa Vialard.
A tropical approach to the compositional piecewise complexity of words and compressed words
Herman Goulet-Ouellet, Valérie Berthé, and Dominique Perrin.
Density of rational languages under shift invariant measures
Miroslav Chodil and Antonín Kucera.
The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic are Highly Undecidable
Gabriel Bathie, Nathanaël Fijalkow, and Corto Mascle.
The Trichotomy of Regular Property Testing
Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, and Saina Sunny.
Approximate Problems for Finite Transducers
Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis, Colin Geniet, Nikolas Mählmann, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk.
Separability properties of monadically dependent graph classes
Simon Iosti, Denis Kuperberg, and Quentin Moreau. Positive and monotone fragments of FO and LTL
Fabian Lenke, Stefan Milius, Henning Urbat, and Thorsten Wissmann.
Algebraic Language Theory with Effects
Nikolay Bazhenov, Dariusz Kalociński, and Michał Wrocławski.
Online and Feasible Presentability: From Trees to Modal Boolean Algebras
Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander.
Probabilistic and Causal Satisfiability: Constraining the model
Jacek Krzaczkowski, Piotr Kawałek, and Paweł M. Idziak.
Nonuniform Deterministic Finite Automata over finite algebraic structures
Manuel Bodirsky, Georg Loho, and Mateusz Skomra.
Reducing Stochastic Games to Semidefinite Programming
Toghrul Karimov.
Verification of Linear Dynamical Systems via O-Minimality of the Real Numbers
Thomas Colcombet, Amina Doumane, and Denis Kuperberg.
Tree algebras and bisimulation-invariant MSO on finite graphs
