Accepted Papers
Paper title and author changes will not be made to this page. The online program will reflect the most up-to-date presentation details, and is scheduled for posting in November.
A well-separated pair decomposition for low density graphs
Joachim Gudmundsson, Sampson Wong
Problems from Optimization and Computational Algebra Equivalent to Hilbert’s Nullstellensatz
Sagnik Dutta, Markus Bläser, Gorav Jindal
k-SUM Hardness Implies Treewidth-SETH
Michael Lampis
On the Usefulness of Promises
Per Austrin, Johan Håstad, Björn Martinsson
The Complexity of Counting Small Sub-Hypergraphs
Holger Dell, Julian Brinkmann, Marc Roth, Marco Bressan, Philip Wellnitz
A parameterized linear formulation of the integer hull
Friedrich Eisenbrand, Thomas Rothvoss
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
Hans L. Bodlaender, Fedor V. Fomin, Tuukka Korhonen
Detecting correlation efficiently in stochastic block models: breaking Otter’s threshold by counting decorated trees
Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li
H-Planarity and Parametric Extensions: when Modulators Act Globally
Fedor Fomin, Petr A. Golovach, Laure Morelle, Dimitrios Thilikos
Dynamic 3D Convex Hulls Revisited and Applications
Haitao Wang
ON DETERMINISTICALLY FINDING AN ELEMENT OF HIGH ORDER MODULO A COMPOSITE
Ziv Oznovich, Ben Lee Volk
Computational Complexity in Property Testing
Renato Ferreira Pinto Jr., Diptaksho Palit, Sofya Raskhodnikova
Prophet Inequality from Samples: Is the More the Merrier?
Tomer Ezra
A Classical Quadratic Speedup for Planted kxor
Meghal Gupta, William He, Ryan O'Donnell, Noah Singer
Evasive sets, twisted varieties, and container-clique trees
Jeck Lim, Jiaxi Nie, Ji Zeng
Coloring 3-Colorable Graphs with Low Threshold Rank
Jun-Ting Hsieh
Centered colorings in minor-closed graph classes
Jędrzej Hodor, Hoang La, Piotr Micek, Clément Rambaud
Lower Bounds for CSP Hierarchies Through Ideal Reduction
Jonas Conneryd, Yassine Ghannane, Shuo Pang
Contract Design Beyond Hidden Actions
Tomer Ezra, Stefano Leonardi, Matteo Russo
Catching Rats in H-minor-free Graphs
Maximilian Gorsky, Giannos Stamoulis, Dimitrios Thilikos, Sebastian Wiederrecht
Numerical Linear Algebra in Linear Space
Yiping Liu, Hoai-An Nguyen, Junzhao Yang
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Rishi Chandra, Michael Dinitz, Chenglin Fan, Zongrui Zou
Tight Lower Bounds for Central String Queries in Compressed Space
Dominik Kempa, Tomasz Kociumaka
Listing faces of polytopes
Nastaran Behrooznia, Sofia Brenner, Arturo Merino, Torsten Mütze, Christian Rieck, Francesco Verciani
Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets
Noga Alon, Shakhar Smorodinsky
Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
Antoine El-Hayek, Monika Henzinger, Jason Li
A Post-Quantum Lower Bound for the Distributed Lovász Local Lemma
Sebastian Brandt, Tim Göttlicher
Online Resource Allocation with Concave Diminishing-Returns Objectives
Kalen Patton
A near-optimal Quadratic Goldreich-Levin algorithm
Jop Briet, Davi Castro-Silva
Combinatorial Selection with Costly Information
Dimitrios Christou, Shuchi Chawla, Ziv Scully, Amit Harlev
On the Computation of Kernels
Oscar Fontaine, Vincent Delecroix, Francis Lazarus
Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri
An Optimal Online Algorithm for Robust Flow Time Scheduling
Anupam Gupta, Amit Kumar, Debmalya Panigrahi, Zhaozi Wang
The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders
Frederick Qiu, Qianfan Zhang, S. Matthew Weinberg
Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
William Kuszmaul, Jingxun Liang, Renfei Zhou
Feature Selection and Junta Testing are Statistically Equivalent
Nathaniel Harms, Lorenzo Beretta, Caleb Koch
Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment
Benjamin Holmgren, Pankaj K. Agarwal, Alex Steiger
Circuits and Backdoors: Five Shades of the SETH
Michael Lampis
Beating full state tomography for unentangled spectrum estimation
Angelos Pelecanos, Xinyu Tan, Ewin Tang, John Wright
Spectral clustering in birthday paradox time
Michael Kapralov, Ekaterina Kochetkova, Weronika Wrzos-Kaminska
Braiding vineyards
Erin Chambers, Christopher Fillmore, Elizabeth Stephenson, Mathijs Wintraecken
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
maximilian probst, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan
RUMOUR SPREADING DEPENDS ON THE LATENT GEOMETRY AND DEGREE DISTRIBUTION IN SOCIAL NETWORK MODELS
Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, Konstantin Sturm
On sampling two spin models using the local connective constant
Charilaos Efthymiou
An optimal algorithm for average distance in typical regular graphs
Alexandros Eskenazis, Manor Mendel, Assaf Naor
Online 3-Taxi on General Metrics
Christian Coester, Tze-Yang Poon
On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions
Natan Rubin
Learning Packing and Covering from Samples
Anupam Gupta, Marco Molinaro
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Jiale Chen, Aaron Bernstein
Determinization of Min-Plus Weighted Automata is Decidable
Shaull Almagor, Guy Arbel, Sarai Sheinvald
Minimum $s$--$t$ Cuts with Fewer Cut Queries
Danupon Nanongkai, Yonggang Jiang, Pachara Sawettamalya
A Broader View on Clustering under Cluster-Aware Norm Objectives
Martin G. Herold, Evangelos Kipouridis, Joachim Spoerhase
The Power of Matching for Online Fractional Hedonic Games
Martin Bullinger, René Romen, Alexander Schlenga
Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
Lisa Hellerstein, Benedikt Plank, Kevin Schewior
Hallucinating Flows for Optimal Mechanisms
Marios Mertzanidis, Athina Terzoglou
Deterministic Edge Colouring
Aleksander Bjørn Grodt Christiansen
Improved Maximin Share Guarantee for Additive Valuations
Ehsan Heidari, Alireza Kaviani, Masoud Seddighin
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Pravesh K Kothari, Jeff Xu
Testing forbidden order-pattern properties on hypergrids
Harish Chandramouleeswaran, Ilan Newman, Tomer Pelleg, Nithin Varma
A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Shyan Akmal, Amir Abboud, Nick Fischer
Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
Omrit Filtser, Tzalik Maimon, Ofir Yomtovyan
Local Gibbs sampling beyond local uniformity
Hongyang Liu, Chunyang Wang, Yitong Yin
Does block size matter in randomized block Krylov low-rank approximation?
Raphael Meyer, Tyler Chen, Ethan Epperly, Christopher Musco, Akash Gopinath Rao
Halfspaces are hard to test with relative error
Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence
Weiming Feng, Minji Yang
Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
Nicolas Menand, Erik Waingarten
On the quantum chromatic gap
Lorenzo Ciardo
Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing
Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi
Persuasive Calibration
Yiding Feng, Wei Tang
The directed disjoint paths problem with congestion
Amelie Heindl; Dario Giuliano Cavallaro; Johannes Christoph Benjamin Schröder; Stephan Kreutzer; Matthias Bentert; Ken-ichi Kawarabayashi
Nearly Tight Sample Complexity for Matroid Online Contention Resolution
Moran Feldman, Ola Svensson, Rico Zenklusen
Optimal mass estimation in the conditional sampling model
Tomer Adar, Eldar Fischer, Amit Levi
Dichotomy for orderings?
Gábor Kun, Jaroslav Nešetřil
Weighted $k$-Server Admits an Exponentially Competitive Algorithm
Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar
Approximate Light Spanners in Planar Graphs
Hung Le, Shay Solomon, Cuong Than, Csaba D. Tóth, Tianyi Zhang
Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
Dominik Kempa, Tomasz Kociumaka
Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
Shahar Lewkowicz, Yossi Azar
Existence of Fair and Efficient Allocation of Indivisible Chores
Ryoga Mahara
Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
Zhongtian He, Matija Bucic, Shang-En Huang, Thatchaphol Saranurak
One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer
Derandomizing Pseudopolynomial Algorithms for Subset Sum
Timothy M. Chan
The Erdős-Pósa property for circle graphs as vertex-minors
Rutger Campbell, J. Pascal Gollin, Meike Hatzel, O-joung Kwon, Rose McCarty, Sang-Il Oum, Sebastian Wiederrecht
PageRank Centrality in Directed Graphs with Bounded In-Degree
Mikkel Thorup, Hanzhi Wang, Zhewei Wei, Mingji Yang
Sample-efficient Replicable Median in Polynomial Time
Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari, Samira Goudarzi, MohammadTaghi Hajiaghayi
Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
Bertrand Even, Christophe Giraud, Nicolas Verzelen
Entrywise Approximation for Matrix Inversion and Linear Systems
Mehrdad Ghadiri, Hoai-An Nguyen, Junzhao Yang
Selfish, local and online scheduling via vector fitting
Danish Kashaev
Collaborative Prediction: Tractable Information Aggregation via Agreement
Natalie Collina, Ira Globus-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, Mirah Shi
Combinatorial Philosopher Inequalities
Enze Sun, Zhihao Gavin Tang, Yifan Wang
Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
Fedor Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, Meirav Zehavi
Balanced Spanning Tree Distributions Have Separation Fairness
Harry Chen, Kamesh Munagala, Govind S. Sankar
A CSP approach to Graph Sandwich Problems
Manuel Bodirsky, Santiago Guzmán Pro
Faster negative length shortest paths by bootstrapping hop reducers
Yufan Huang, Peter Jin, Kent Quanrud
Networked Information Aggregation via Machine Learning
Michael Kearns, Aaron Roth, Emily Ryu
Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective
Lin Chen, Yuchen Mao, Guochuan Zhang
Balls and Bins and the Infinite Process with Random Deletions
Petra Berenbrink, Tom Friedetzky, Peter Kling, Lars Nagel
Traversing regions of supersolvable hyperplane arrangements and their lattice quotients
Sofia Brenner, Jean Cardinal, Thomas McConville, Arturo Merino, Torsten Mütze
Quantum State Preparation with Optimal T-Count
David Gosset, Robin Kothari, Kewen Wu
A quasi-polynomial bound for the minimal excluded minors for a surface
Sarah Houdaigoui, Ken-ichi Kawarabayashi
Short circuit walks in fixed dimension
Alexander Black, Christian Nöbel, Raphael Steiner
Nearly Optimal Bounds for Stochastic Online Sorting
Yang Hu
Universal Connection Schedules for Reconfigurable Networking
Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, Tegan Wilson, Ruogu Zhang
Helly-type theorems for splitting point sets
Lidor Portal, Natan Rubin
Hardness of Approximation for Shortest Path with Vector Costs
Charlie Carlson, Yury Makarychev, Ron Mosenzon
Computing the Heaviest Disk and Related Problems
Pankaj K Agarwal, Esther Ezra, Micha Sharir
A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
Marc Dufay, Roger Wattenhofer
Online Proportional Apportionment
Javier Cembrano, Jose Correa, Svenja M. Griesbach, Victor Verdugo
Rapid mixing for Gibbs states within a logical sector: a dynamical view of self-correcting quantum memories
Thiago Bergamaschi, Reza Gheissari, Yunchao Liu
A Few Good Choices
Haoyu Song, Thanh Nguyen, Young-San Lin
(Almost) Perfect Discrete Iterative Load Balancing
Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Hamed Hosseinpour, Dominik Kaaser, Peter Kling, Thomas Sauerwald
On a clique game and the Erdős-Hajnal problem on high-chromatic high-girth subgraphs
Seth Pettie, Gábor Tardos, Bartosz Walczak
New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivny
Space-efficient population protocols for exact majority in general graphs
Joel Rybicki, Jakob Solnerzik, Olivier Stietel, Robin Vacus
Time-Biased Random Walks and Robustness of Expanders
Sam Olesker-Taylor, Thomas Sauerwald, John Sylvester
History-Independent Load Balancing
Michael Bender, William Kuszmaul, Elaine Shi, Rose Silver
Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, Francesco d'Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, Jukka Suomela
Algebraic Closure of Matrix Sets Recognized by 1-VASS
Rida Ait El Manssour, Mahsa Naraghi, Mahsa Shirmohammadi, James Worrell
Perfect Matchings in Random Sparsifications of Dense Hypergraphs
Jie Han, Jingwen Zhao
A Near-Complete Resolution of the Exponential-Time Complexity of k-opt for the Traveling Salesman Problem
Sophia Heimann, Hung Hoang, Stefan Hougardy
Augmenting to 4-vertex connectivity is fixed-parameter tractable
Johannes Carmesin, M. S. Ramanujan
Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
Jon Nelson, Joel Rajakumar, Dominik Hangleiter, Michael J. Gullans
Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
Vihan Shah
Improved Additive Approximation Algorithms for APSP
Ce Jin, Yael Kirkpatrick, Michał Stawarz, Virginia Vassilevska Williams
Dynamic Hierarchical j-Tree Decomposition and Its Applications
Gramoz Goranci, Monika Henzinger, Peter Kiss, Ali Momeni, Gernot Zöcklein
Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
Daniel Paul-Pena, C. Seshadhri
Vizing’s Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, Tianyi Zhang
Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Kobbi Nissim, Eliad Tsfadia, Chao Yan
Is nasty noise actually harder than malicious noise?
Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio
A Tutte-type canonical decomposition of 3- and 4-connected graphs
Jan Kurkofka; Tim Planken
Tree Embedding in High Dimensions: Dynamic and Massively Parallel
Gramoz Goranci, Shaofeng H.-C. Jiang, Peter Kiss, Qihao Kong, Yi Qian, Eva Szilagyi
On the Universality of Round Elimination Fixed Points
Alkida Balliu, Sebastian Brandt, Ole Gabsdil, Dennis Olivetti, Jukka Suomela
When Contracts Get Complex: Information-Theoretic Barriers
Paul Duetting, Michal Feldman, Yoav Gal-Tzur
Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
Anna Lunghi, Matteo Castiglioni, Alberto Marchesi
Optimal Rounding for Two-Stage Bipartite Matching
Tristan Pollner, Amin Saberi, Anders Wikum
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
Approximate Counting of Permutation Patterns
Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava
On the edge expansion of random polytopes
Marcelo Sales, Asaf Ferber, Michael Krivelevich, Wojciech Samotij
Bounding the asymptotic quantum value of all multipartite compiled non-local games
Matilde Baroni, Dominik Leichtle, Siniša Janković, Ivan Šupić
Burling graphs in graphs with large chromatic number
Tara Abrishami, Marcin Briański, James Davies, Xiying Du, Jana Masaříková, Paweł Rzążewski, Bartosz Walczak
History-Independent Maximal Matchings Can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees
Rathish Das, William Kuszmaul
Sublinear Metric Steiner Forest via Maximal Independent Set
Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
Local Search for Clustering in Almost-linear Time
Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, Pinyan Lu
Nearly Tight Bounds for the Online Sorting Problem
Yossi Azar, Debmalya Panigrahi, Or Vardi
Constructive l2-Discrepancy Minimization with Additive Deviations
Kunal Dutta
Faster algorithms for packing forests in graphs and related problems
Pavel Arkhipov, Vladimir Kolmogorov
#CFG and #DNNF admit FPRAS
Alexis de Colnet, Kuldeep S. Meel
Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin, Jacobus Conradi, Ce Jin, André Nusser, Carolin Rehs
Sensitivity Lower Bounds for Approximation Algorithms
Noah Fleming, Yuichi Yoshida
Online Conformal Prediction with Efficiency Guarantees
Vaidehi Srinivas
Online Orthogonal Vectors Revisited
Karthik Gajulapalli, Alexander Golovnev, Samuel King, Sidhant Saraogi
All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
Yotam Kenneth-Mordoch, Robert Krauthgamer
Phase transition of the Sinkhorn-Knopp algorithm
Kun He
On Independent Spanning Trees in Random Graphs
Liana Yepremyan, Keith Frankston, Alexey Pokrovskiy, Nemanja Draganic, Michael Krivelevich
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Contract Design for Sequential Actions
Maya Schlesinger, Tomer Ezra, Michal Feldman
The Complexity of Dynamic LZ77 is $\tilde Θ(n^{2/3})$
Itai Boneh, Shay Golan, Matan Kraus
Sparsifying Cayley Graphs on Every Group
Jun-Ting Hsieh, Daniel Lee, Sidhanth Mohanty, Aaron Putterman, Rachel Yun Zhang
Embedding into Spanning Trees is No Harder than Finding Good Hierarchical Partitions
Willem Fletcher, D Ellis Hershkowitz
Language Generation in the Limit: Noise, Loss, and Feedback
Yannan Bai, Debmalya Panigrahi, Ian Zhang
Better Bounds for Semi-Streaming Single-Source Shortest Paths
Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan
Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
Michał Dereziński, Aaron Sidford
Robust Equilibria in Shared Resource Allocation via Strengthening Border’s Theorem
David X. Lin, Giannis Fikioris, Siddhartha Banerjee, Eva Tardos
Unbounded Error Correcting Codes
Klim Efremenko, Or Zamir
Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
Bowie Liu, Dennis Wong, Chan-Tong Lam, Sio-Kei Im
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka
Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
Manuel Christalla, Luise Puhlmann, Vera Traub
Additive Approximation Schemes for Low-Dimensional Embeddings
Prashanti Anderson, Ainesh Bakshi, Sam Hopkins
Three-edge-coloring (Tait coloring) cubic graphs and nowhere-zero 4-flow for graphs on the torus
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe
Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning
Siddharth Barman; Paritosh Verma
An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the k-Means Problem
Vincent Cohen-Addad, Fabian Kuhn, Zahra Parsaeian
MAX BISECTION might be harder to approximate than MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Excluding a Line Minor via Design Matrices and Column Bounds for the Circuit Imbalance Measure
Neta Singer, Daniel Dadush, Friedrich Eisenbrand, Rom Pinchasi, Thomas Rothvoss
An Optimal Density Bound for Discretized Point Patrolling
Ahan Mishra
Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
Kuan Cheng, Ruiyang Wu
Coloring Graphs with Few Colors in the Streaming Model
Sepehr Assadi, Janani Sundaresan, Helia Yazdanyar
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, Thatchaphol Saranurak
Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
Online Learning with Limited Information in the Sliding Window Model
Vladimir Braverman, Sumegha Garg, Chen Wang, David P Woodruff, Samson Zhou
Tree covers of size 2 for the Euclidean plane.
Artur Bikeev, Andrey Kupavskii, Maxim Turevskii
Downward self-reducibility in the total function polynomial hierarchy
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi
A (2+ε)-approximation algorithm for the general scheduling problem in quasipolynomial time
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Ndiame Ndiaye, Max Dupre la Tour, Manuel Lafond
THE DIVISION BARRIER: OPTIMAL BOUNDS AND STRUCTURAL LIMITS IN TOOM-COOK INTERPOLATION
Yuval Spiizer, Oded Schwartz, Roy Nissim
On the Complexity of the Skolem Problem at Low Orders
Piotr Bacik, Joël Ouaknine, James Worrell
Near-Optimal Four-Cycle Counting in Graph Streams
Sebastian Lüderssen, Stefan Neumann, Pan Peng
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Maximilian Probst Gutenberg, Simon Meierhans
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
$(\alpha, \beta)$ Spanners and Hybrid Spanners with Nearly Tight Bounds
Gur Lifshitz, Shiri Chechik
Distributed Interactive Proofs for Planarity with Log-Star Communication
Yuval Gil, Merav Parter
Matroids are Equitable
Hannaneh Akrami, Roshan Raj, László A. Végh
Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong
Shortcuts and Transitive-Closure Spanners Aproximation
Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
Efficient Online Random Sampling via Randomness Recycling
Thomas Draper, Feras Saad
Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension
Kunal Dutta, Karol Pisula
Optimal randomized clustering for subsets of $L_p$ when $p\ge 2$
Assaf Naor, Kevin Ren
A Better-Than-5/4-Approximation for Two-Edge Connectivity
Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu
An unconditional lower bound for the active-set method in convex quadratic maximization
Eleon Bach, Yann Disser, Sophie Huiberts, Nils Mosis
Spectral Clustering with Side Information
Hendrik Fichtenberger, Michael Kapralov, Ekaterina Kochetkova, Silvio Lattanzi, Davide Mazzali, Weronika Wrzos-Kaminska
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Daniel Dadush, James B. Orlin, Aaron Sidford, László A. Végh
Space-Efficient $k$-Mismatch Text Indexes
Tomasz Kociumaka, Jakub Radoszewski
Distributional Sparse Vector Techniques and Applications to Privacy under Continual Observation
Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay
Contextual Search in Principal-Agent Games: The Curse of Degeneracy
Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan
Explicit Min-wise Hash Families with Optimal Size
Xue Chen, Shengtang Huang, Xin Li
Interaction between skew-representability, tensor products, extension properties, and rank inequalities
Kristof Berczi, Boglarka Geher, Andras Imolay, Laszlo Lovasz, Carles Padro, Tamas Schwarcz
Finite Pinwheel Scheduling: the k-Visits Problem
Sotiris Kanellopoulos, Maria Kokkou, Euripides Markou, Aris Pagourtzis, Christos Pergaminelis
Augmenting Packing Dynamic Programs to Handle (Many) Additional Budget Constraints
Alexander Armbruster, Fabrizio Grandoni, Antoine Tinguely, Andreas Wiese
Compatibility of Fairness and Nash Welfare under Subadditive Valuations
Siddharth Barman, Mashbat Suzuki
Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
Hadley Black, Christopher Ye
Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
Vikrant Ashvinkumar, Mursalin Habib, Shashank Srivastava
Faster Distributed ∆-Coloring via a Reduction to MIS
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
New Oracles and Labeling Schemes for Vertex Cut Queries
Yonggang Jiang, Merav Parter, Asaf Petruschka
Approximately Dominating Sets in Elections
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang
Learning in an Echo Chamber: Online Learning with Replay Adversary
Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, Amartya Sanyal
$L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
Honghao Lin, Zhao Song, David P. Woodruff, Shenghao Xie, Samson Zhou
A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
Meike Neuwohner, Michael Zlatin, Olha Silina
On Distributed Colouring of Hyperbolic Random Graphs
Janosch Ruff, Yannic Maus
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Maximilian Probst Gutenberg, Simon Meierhans, Thatchaphol Saranurak
Likelihood of the Existence of Average Justified Representation
Qishen Han, Biaoshuai Tao, Lirong Xia, Chengkai Zhang, Houyu Zhou
Optimization Modulo Integer Linear-Exponential Programs
Alessio Mansutti, Guruprerana Shabadi, S Hitarth
Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Andreas Göbel, Nicolas Klodt, George Skretas, John Sylvester, Viktor Zamaraev
Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications
Vinod Vaikuntanathan, Or Zamir
Covering the Euclidean Plane by a Pair of Trees
Hung Le, Lazar Milenković, Shay Solomon, Tianyi Zhang
Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
Jason Gaitonde, Elchanan Mossel
Unsplittable Flow Cut Gap in Undirected Graphs
David Aleman Espinosa, Nikhil Kumar, Joseph Poremba, Bruce Shepherd
Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
Rajat De, Dominik Kempa
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, More General
David Shmoys, Varun Suriyanarayana, Seeun William Umboh
Quantum Advantage via Solving Multivariate Polynomials
Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou, Amit Sahai
Quantum Hamiltonian Certification
Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, Qi Zhao
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
Efficiently Constructing Sparse Navigable Graphs
Richard Wen, Yarin Shechter, Christopher Musco, Alex Conway, Martin Farach-Colton, Laxman Dhulipala, Ben Landrum, Torsten Suel, Rob Johnson
Tight Differentially Private PCA via Matrix Coherence
Tommaso d'Orsi, Gleb Novikov
Lower bounds for the universal TSP on the plane
Cosmas Kravaris
On the Structure of Replicable Hypothesis Testers
Anders Aamand, Maryam Aliakbarpour, Justin Chen, Shyam Narayanan, Sandeep Silwal
Plane vs. Plane Low Degree Test
Silas Richelson, Amey Bhangale
Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
Jason Li, Connor Mowry, Satish Rao
Improved Approximation for Ranking on General Graphs
Tao Yu, Mahsa Derakhshan, Mohammad Roghani, Mohammad Saneian
Online Connectivity Augmentation
Mohit Garg, Aditya Subramanian
Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets
Riccardo Colini Baldeschi, Sophie Klumper, Twan Kroll, Stefano Leonardi, Guido Schaefer, Artem Tsikiridis
A Classification of Long-Refinement Graphs for Colour Refinement
Sandra Kiefer, T. Devini de Mel
Stochastic Embedding of Digraphs into DAGs
Arnold Filtser
Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang