Paper titles and author information appears as submitted.
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.
(Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems
Timothy M. Chan
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani
A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
Neeraj Kumar, Daniel Lokshtanov, Saket Saurabh, Subhash Suri
A Deterministic Parallel APSP Algorithm and its Applications
Adam Karczmarz, Piotr Sankowski
A Fast Minimum Degree Algorithm and Matching Lower Bound
Robert Cummings, Matthew Fahrbach, Animesh Fatehpuria
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Wegrzycki
A Fine-Grained Perspective on Approximating Subset Sum and Partition
Karl Bringmann, Vasileios Nakos
A Local Search Framework for Experimental Design
Lap Chi Lau, Hong Zhou
A Lower Bound for Dynamic Fractional Cascading
Peyman Afshani
A Refined Laser Method and Faster Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Delegation
Marcel Dall'Agnol, Tom Gur, Oded Lachish
A tight condition for triangle factors in pseudorandom graphs
Patrick Morris
A Time-Optimal Randomized Parallel Algorithm for MIS
Mohsen Ghaffari, Bernhard Haeupler
A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting
Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis
Algorithms for Persuasion with Limited Communication
Ronen Gradwohl, Niklas Hahn, Martin Hoefer, Rann Smorodinsky
Algorithms for weighted independent transversals and strong colouring
Alessandra Graf, David Harris, Penny Haxell
All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier
Fabrizio Grandoni, Giuseppe F. Italiano, Aleksander Łukasiewicz, Nikos Parotsidis, Przemysław Uznański
An $\tilde{O}(n^{5/4})$ Time $\varepsilon$-Approximation Algorithm for RMS Matching in a Plane
Nathaniel Lahn, Sharath Raghvendra
An Efficient Epsilon-BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
Yang Cai, Argyris Oikonomou, Grigoris Velegkas, Mingfei Zhao
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures
Jin-Yi Cai, Tianyu Liu
An improved procedure for colouring graphs of bounded local density
Eoin Hurley, Rémi de Joannis de Verclos, Ross J. Kang
Analytic quantum weak coin flipping protocols with arbitrarily small bias
Atul Singh ARORA, Jérémie ROLAND, Chrysoula VLACHOU
Approximate Distance Oracles Subject to Multiple Vertex Failures
Ran Duan, Yong Gu, Hanlin Ren
Approximate Evaluation of First-Order Counting Queries
Jan Dreier, Peter Rossmanith
Approximate Nearest Neighbors Beyond Space Partitions
Alexandr Andoni, Aleksandar Nikolov, Ilya Razenshteyn, Erik Waingarten
Approximating $(k,\ell)$-Median Clustering for Polygonal Curves
Maike Buchin, Anne Driemel, Dennis Rohde
Approximating pathwidth for graphs of small treewidth
Carla Groenland, Gwenaël Joret, Wojciech Nadara, Bartosz Walczak
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
Zhihan Jin, Zhengfeng Ji, Pinyan Lu
Approximating the Median under the Ulam Metric
Diptarka Chakraborty, Debarati Das, Robert Krauthgamer
Approximation Algorithms and Hardness for Strong Unique Games
Suprovat Ghoshal, Anand Louis
Asymptotic dimension of minor-closed families and beyond
Chun-Hung Liu
Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model
Michael Goodrich, Riko Jacob, Nodari Sitchinava
Average Sensitivity of Graph Algorithms
Nithin Varma, Yuichi Yoshida
Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
Mahsa Derakhshan, David Pennock, Aleksandrs Slivkins
Beating the probabilistic lower bound on perfect hashing
Chaoping Xing, Chen Yuan
Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners
Peter Robinson
Beyond Submodular Maximization via One-Sided Smoothness
Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
Jana Cslovjecsek, Friedrich Eisenbrand, Christoph Hunkenschröder, Lars Rohwedder, Robert Weismantel
Branch-and-Bound Solves Random Binary Packing IPs in Polytime
Yatharth Dubey, Santanu Dey, Marco Molinaro
Can We Beat the AKS Sorting Network?
Gilad Asharov, Wei-Kai Lin, Elaine Shi
Coloring and Maximum Weight Independent Set of Rectangles
Parinya Chalermsook, Bartosz Walczak
Competitive Allocation of a Mixed Manna
Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta
Competitive Data-Structure Dynamization
Claire Mathieu, Rajmohan Rajaraman, Neal Young, Arman Yousefi
Concentration bounds for almost k-wise independence with applications to non-uniform security
Nick Gravin, Siyao Guo, Tsz Chiu Kwok, Pinyan Lu
Connecting Robust Shuffle Privacy and Pan-Privacy
Victor Balcer, Albert Cheu, Matthew Joseph, Jieming Mao
Consistent k-Clustering for General Metrics
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson
Constrained-Order Prophet Inequalities
Makis Arsenis, Odysseas Drosis, Robert Kleinberg
Coresets for Clustering in Excluded-minor Graphs and Beyond
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan Wu
Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
Jacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Zivny
Counting Small Permutation Patterns
Chaim Even-Zohar, Calvin Leng
Decomposing the Complement of the Union of Cubes in Three Dimensions
Pankaj K. Agarwal, Micha Sharir, Alex Steiger
Deep Weisfeiler Leman
Martin Grohe, Pascal Schweitzer, Daniel Wiebking
Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
Julia Chuzhoy, Thatchaphol Saranurak
Deterministic Replacement Path Covering
Karthik C. S., Merav Parter
Dimension-Preserving Reductions Between SVP and CVP in Different $p$-Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar, Zeyong Li, Noah Stephens-Davidowitz
Directed Shortest Paths via Approximate Cost Balancing
James B. Orlin, László Végh
Distributed Metropolis Sampler with Optimal Parallelism
Weiming Feng, Thomas P. Hayes, Yitong Yin
Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
Krzysztof Nowicki, Krzysztof Onak
Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
Sebastian Forster, Gramoz Goranci, Monika Henzinger
Dynamic Set Cover: Improved Amortized and Worst-Case Update Times
Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, Xiaowei Wu
Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting
Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
Kuan Cheng, Xin Li
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk, Manuel Sorge, Bartłomiej Wróblewski, Anna Zych-Pawlewicz
Efficient Linear and Affine Codes for Correcting Insertions/Deletions
Kuan Cheng, Venkatesan Guruswami, Bernhard Haeupler, Xin Li
EPTAS for $k$-means Clustering of Affine Subspaces
Eduard Eiben, Fedor Fomin, Petr A. Golovach, Willian Lochet, Fahad Panolan, Kirill Simonov
Estimating the Nash Social Welfare for coverage and other submodular valuations
Jan Vondrak, Wenzheng Li
Explicit two-deletion codes with redundancy matching the existential bound
Venkatesan Guruswami, Johan Håstad
Fast Convergence of Fictitious Play for Diagonal Payoff Matrices
Jacob Abernethy, Kevin A. Lai, Andre Wibisono
Fast Low-Space Algorithms for Subset Sum
Ce Jin, Nikhil Vyas, Ryan Williams
Fine-grained hardness of CVP(P)—Everything that we can prove (and nothing else)
Divesh Aggarwal, Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
FPT Approximation for FPT Problems
Daniel Lokshtanov, Pranabendu Misra, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Arnold Filtser, Michael Kapralov, Navid Nouri
Hamiltonicity of random subgraphs of the hypercube
Alberto Espuny Díaz, Padraig Condon, António Girão, Daniela Kühn, Deryk Osthus
Hardness of Approximation for Orienteering with Multiple Time Windows
Naveen Garg, Sanjeev Khanna, Amit Kumar
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga
How to Morph Graphs on the Torus
Erin Wolf Chambers, Jeff Erickson, Patrick Lin, Salman Parsa
Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting
Itai Dinur
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali
Improved Deterministic Network Decomposition
Mohsen Ghaffari, Christoph Grunau, Vaclav Rozhon
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
Improving the dilation of a metric graph by adding edges
Joachim Gudmundsson, Sampson Wong
Incremental Single Source Shortest Paths in Sparse Digraphs
Shiri Chechik, Tianyi Zhang
Induced subgraphs of bounded treewidth and the container method
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour
Infinite-Duration All-Pay Bidding Games
Guy Avni, Ismael Jecker, Djordje Zikelic
Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs
Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts
List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
Ainesh Bakshi, Pravesh K. Kothari
Local Statistics, Semidefinite Programming, and Community Detection
Jess Banks, Sidhanth Mohanty, Prasad Raghavendra
Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions
Karthekeyan Chandrasekaran, Chandra Chekuri
Minimizing Convex Functions with Integral Minimizers
Haotian Jiang
Minimum-cost integer circulations in given homology classes
Sarah Morell, Ina Seidel, Stefan Weltge
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
Suman Kalyan Bera, Noujan Pashanasangi, C. Seshadhri
Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
Timothy M. Chan
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara, Nobutaka Shimizu
New Data Structures for Orthogonal Range Reporting and Range Minima Queries
Yakov Nekrich
New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
Jin-Yi Cai, Zhiguo Fu, Shuai Shao
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst, Virginia Vassilevska Williams, Nicole Wein
Non-linear Hamilton cycles in linear quasi-random hypergraphs
Jie Han, Xichao Shu, Guanghui Wang
Non-Separable Dynamic Mechanism Design
Santiago Balseiro, Vahab Mirrokni, Renato Paes Leme, Song Zuo
Non-uniform Geometric Set Cover and Scheduling on Multiple Machines
Jatin Batra, Nikhil Bansal
On a combinatorial generation problem of Knuth
Arturo Merino, Ondřej Mička and Torsten Mütze
On Approximability of Clustering Problems Without Candidate Centers
Vincent Cohen-Addad, Karthik C. S., Euiwoong Lee
On Efficient Distance Approximation for Graph Properties
Nimrod Fiat, Dana Ron
On Indexing and Compressing Finite Automata
Nicola Cotumaccio, Nicola Prezza
On Locating Paths in Compressed Tries
Nicola Prezza
On Multi-Dimensional Gains from Trade Maximization
Yang Cai, Kira Goldner, Steven Ma, Mingfei Zhao
On Near-Linear-Time Algorithms for Dense Subset Sum
Karl Bringmann, Philip Wellnitz
On Testability of First-Order Properties in Bounded-Degree Graphs
Isolde Adler, Noleen Köhler, Pan Peng
On the Competitive Analysis and High Accuracy Optimality of Profile Maximum Likelihood
Yanjun Han, Kirankumar Shiragur
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
On the Orbit Closure Containment Problem and Slice Rank of Tensors
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey, Frank-Olaf Schreyer
On Two-Handed Planar Assembly Partitioning
Pankaj Agarwal, Boris Aronov, Tzvika Geft, Dan Halperin
Online Combinatorial Auctions
Yuan Deng, Debmalya Panigrahi, Hanrui Zhang
Online Discrepancy Minimization for Stochastic Arrivals
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Edge Coloring Algorithms via the Nibble Method
Sayan Bhattacharya, Fabrizio Grandoni, David Wajc
Online Generalized Network Design Under (Dis)Economies of Scale
Viswanath Nagarajan, Lily Wang
Online Multiserver Convex Chasing and Optimization
Mark Sellke, Sebastien Bubeck, Yuval Rabani
Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation
Arvind Mahankali, David P. Woodruff
Optimal Contextual Pricing and Extensions
Allen Liu, Renato Paes Leme, Jon Schneider
Optimal Discretization is Fixed-parameter Tractable
Stefan Kratsch, Tomáš MasaÅ™Ãk, Irene Muzi, Marcin Pilipczuk, Manuel Sorge
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness
Dana Ron, Asaf Rosin
Optimal Girth Approximation for Dense Directed Graphs
Shiri Chechik, Gur Lifshitz
Optimal Inapproximability with Universal Factor Graphs
Per Austrin, Jonah Brown-Cohen, Johan Håstad
Optimal Oblivious Priority Queues
Zahra Jafargholi, Kasper Green Larsen, Mark Simkin
Optimal Vertex Fault-Tolerant Spanners in Polynomial Time
Greg Bodwin, Michael Dinitz, Caleb Robelle
Peeling Close to the Orientability Threshold – Spatial Coupling in Hashing-Based Data Structures
Stefan Walzer
Planar Distance Oracles with Better Time-Space Tradeoffs
Yaowei Long, Seth Pettie
Planar Negative k-Cycle
Pawel Gawrychowski, Shay Mozes, Oren Weimann
Planar Reachability Under Single Vertex or Edge Failures
Giuseppe F. Italiano, Adam Karczmarz, Nikos Parotsidis
Polyhedral value iteration for discounted games and energy games
Alexander Kozachinskiy
Polynomial-time trace reconstruction in the smoothed complexity model
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Population Recovery from the Deletion Channel: Nearly Matching Trace Reconstruction Bounds
Shyam Narayanan
PTAS for Minimum Cost Multi-covering with Disks
Ziyun Huang, Qilong Feng, Jianxin Wang, Jinhui Xu
Quantum algorithms for graph problems with cut queries
Troy Lee, Miklos Santha, Shengyu Zhang
Query strategies for priced information revisited
Guy Blanc, Jane Lange, Li-Yang Tan
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten
Randomized Cup Game Algorithms Against Strong Adversaries
Michael A. Bender, William Kuszmaul
Rankwidth meets stability
Jaroslav Nesetril, Patrice Ossona de Mendez, Michał Pilipczuk, Roman Rabinovich, Sebastian Siebertz
Rapid Mixing for Colorings via Spectral Independence
Zongchen Chen, Andreas Galanis, Daniel Stefankovic, Eric Vigoda
Rapid mixing from spectral independence beyond the Boolean domain
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang
Robust Algorithms for Online Convex Problems
Marco Molinaro
Robust Learning of Mixtures of Gaussians
Daniel M. Kane
Rolling backwards can move you forward: on embedding problems in sparse expanders
Nemanja Draganic, Michael Krivelevich, Rajko Nenadov
Scheduling with Communication Delays via LP Hierarchies and Clustering II: Weighted Completion Times on Related Machines
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, Yihao Zhang
Self-Stabilizing Clock Synchronization with 1-bit Messages
Paul Bastide, George Giakkoupis, Hayk Saribekyan
Shorter Labels for Routing in Trees
Pawel Gawrychowski, Wojciech Janczewski, Jakub Lopuszanski
Shortest Paths Among Obstacles in the Plane Revisited
Haitao Wang
Solving hard cut problems via flow-augmentation
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlstrom
Solving Sparse Linear Systems Faster than Matrix Multiplication
Richard Peng, Santosh Vempala
SOS degree reduction with applications to clustering and robust moment estimation
David Steurer, Stefan Tiegel
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
Michael Kapralov
Spectral Clustering Oracles in Sublinear Time
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler
Spectral Sparsification of Metrics and Kernels
Kent Quanrud
Static and Streaming Data Structures for Fréchet Distance Queries
Arnold Filtser, Omrit Filtser
Streaming Submodular Matching Meets the Primal-Dual Method
Roie Levin, David Wajc
Strong Connectivity Augmentation is FPT
Pranabendu Misra, Kristine Vitting Klinkby, Saket Saurabh
Strongly refuting all semi-random Boolean CSPs
Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
Sublinear Time Algorithms for Longest Increasing Subsequence
Michael Mitzenmacher, Saeed Seddighin
The Connectivity Threshold for Dense Graphs
Anupam Gupta, Euiwoong Lee, Jason Li
The Demand Query Model for Bipartite Matching
Noam Nisan
The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, Zihan Tan
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
Andreas Björklund, Petteri Kaski
The growth rate over trees of any family of sets defined by a monadic second order formula is semi-computable
Matthieu Rosenfeld
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Thomas Bläsius, Tobias Friedrich, Andreas Göbel, Jordi Levy, Ralf Rothenberger
The Min-Cost Matching with Concave Delays Problem
Yossi Azar, Runtian Ren, Danny Vainstein
The Secretary Problem with Independent Sampling
Jose Correa, Andrés Cristi, Laurent Feuilloley, Tim Oosterwijk, Alexandros Tsigonias-Dimitriadis
The shortest disjoint paths problem
Lochet William
Tight Bounds for Online Graph Partitioning
Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid
Tight Bounds for Parallel Paging and Green Paging
Kunal Agrawal, Michael Bender, Rathish Das, William Kuszmaul, Enoch Peserico, Michele Scquizzato
Tight Distributed Listing of Cliques
Keren Censor-Hillel, Yi-Jun Chang, Francois Le Gall, Dean Leitersdorf
Tight Distributed Sketching Lower Bound for Connectivity
Huacheng Yu
Tolerant Distribution Testing in the Conditional Sampling Model
Shyam Narayanan
Towards PTAS for Precedence Constrained Scheduling via Combinatorial Algorithms
Shi Li
Treewidth-Pliability and PTAS for Max-CSPs
Miguel Romero, Marcin Wrochna, Stanislav Zivny
Twin-width II: small classes
Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Tomassé, Rémi Watrigant
Two-stage Stochastic Matching with Application to Ride Hailing
Yiding Feng, Rad Niazadeh, Amin Saberi
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
Arun Jambulapati, Aaron Sidford
Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins
Jasper C.H. Lee, Paul Valiant
Unlinking, splitting, and some other NP-hard problems in knot theory
Dale Koenig, Anastasiia Tsvietkova
Vertex Sparsification for Edge Connectivity
Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yunbum Kook, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz
Which Random Matching Markets Exhibit a Stark Effect of Competition?
Yash Kanoria, Seungki Min, Pengyu Qian