Paper titles and author information appear 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.
*Denotes two talks will be combined and presented as one talk. **Denotes two talks will be combined and presented as one talk.
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, and Zixuan Xu (MIT)
Fair price discrimination Siddhartha Banerjee (Cornell); Kamesh Munagala, and Yiheng Shen (Duke University); Kangning Wang (Stanford University)
The Cost of Parallelizing Boosting Xin Lyu (UC Berkeley); Hongxun Wu (UC Berkeley); Junzhao Yang (Tsinghua University)
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree Rajesh Jayaram, and Vahab Mirrokni (Google Research); Shyam Narayanan (Massachusetts Institute of Technology); Peilin Zhong (Google Research)
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time Jan van den Brand, and Li Chen (Georgia Tech); Rasmus Kyng (ETH Zurich); Yang P. Liu (Stanford University); Richard Peng (University of Waterloo); Maximilian Probst Gutenberg (ETH Zurich); Sushant Sachdeva (University of Toronto); Aaron Sidford (Stanford University)
Viderman’s algorithm for quantum LDPC codes Anirudh Krishna, Inbal Rachel Livni Navon, and Mary Wootters (Stanford University)
Breaking the Metric Voting Distortion Barrier Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang (Stanford University); Hongxun Wu (University of California at Berkeley).
Edge-Coloring Algorithms for Bounded Degree Multigraphs Abhishek Dhawan (Georgia Institute of Technology)
Code sparsification and its applications Sanjeev Khanna (University of Pennsylvania); Aaron (Louie) Putterman, and Madhu Sudan (Harvard University)
Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues Robert Wang, Kam Chuen Tung, and Lap Chi Lau (University of Waterloo)
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization Daniel Gibney (Georgia Institute of Technology); Ce Jin (MIT); Tomasz Kociumaka (Max Planck Institute for Informatics); Sharma V. Thankachan (North Carolina State University)
Dynamically Maintaining the Persistent Homology of Time Series Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Monika Henzinger (Institute of Science and Technolology Austria); Lara Ost (Department of Computer Science, University of Vienna)
A Distributed Palette Sparsification Theorem Maxime Flin (Reykjavik University); Mohsen Ghaffari (MIT); Fabian Kuhn (University of Freiburg); Magnús M. Halldórsson (Reykjavik University); Alexandre Nolin (CISPA – Helmholtz Center for Information Security)
Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem Guanzhong Li, Lvzhou Li, and Jingquan Luo (Sun Yat-sen University)
The Sharp Power Law of Local Search on Expanders Simina Branzei (Purdue University); Davin Choo (National University of Singapore); Nicholas Recker (Purdue University)
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes Édouard Bonnet, and Julien Duron (Univ. Lyon, ENS de Lyon, UCBL, CNRS, LIP, France); John Sylvester, and Viktor Zamaraev (Department of Computer Science, University of Liverpool, UK); Maksim Zhukovskii (Department of Computer Science, University of Sheffield, UK)
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns Parinya Chalermsook (Aalto University); Seth Pettie (University of Michigan); Sorrachai Yingchareonthawornchai (Aalto University)
The Identity Problem in nilpotent groups of bounded class Ruiwen Dong (University of Oxford)
Composition of nested embeddings with an application to outlier removal Shuchi Chawla, and Kristin Sheridan (UT Austin)
Efficient Quantum State Synthesis with One Query Gregory Rosenthal (University of Toronto and University of Warwick)
Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles Yan Alves Radtke, and Stefan Felsner (Technische Universität Berlin); Johannes Obenaus (Freie Universität Berlin); Sandro Roch, and Manfred Scheucher (Technische Universität Berlin); Birgit Vogtenhuber (Graz University of Technology)
On the Extremal Functions of Acyclic Forbidden 0-1 Matrices Seth Pettie (University of Michigan); Gábor Tardos (Rényi Institute, Budapest)
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds Nairen Cao, Shang-En Huang, and Hsin-Hao Su (Boston College)
Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic Jesse Campion Loth (Simon Fraser University, Burnaby, Canada); Tomáš Masařík (University of Warsaw, Warsaw, Poland); Kevin Halasz, and Bojan Mohar (Simon Fraser University, Burnaby, Canada); Robert Šámal (Charles University, Prague, Czech Republic)
Fully dynamic approximation schemes on planar and apex-minor-free graphs Tuukka Korhonen (University of Bergen); Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski (University of Warsaw)
Approximating Subset Sum Ratio faster than Subset Sum Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics)
Bin Packing under Random-Order: Breaking the Barrier of 3/2 Anish Hebbar, Arindam Khan, and K. V. N. Sreenivas (Indian Institute of Science Bengaluru)
On Approximability of Steiner Tree in $ell_p$-metrics Henry Fleischmann (University of Michigan); Surya Teja Gavva, and Karthik C. S. (Rutgers University)
Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D Pankaj Agarwal (Duke University); Esther Ezra (Bar Ilan University); Micha Sharir (Tel Aviv University)
Rationality-Robust Information Design: Bayesian Persuasion under Quantal Response Yiding Feng (University of Chicago); Chien-Ju Ho (Washington University in St. Louis); Wei Tang (Columbia University)
Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings Vishesh Jain (University of Illinois Chicago); Huy Tuan Pham (Stanford University)
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts Zhongtian He (Princeton University); Shang-En Huang (Boston College); Thatchaphol Saranaurak (University of Michigan)
Beyond the Quadratic Time Barrier for Network Unreliability Ruoxu Cen, and William He (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University)
Sparse induced subgraphs in $P_6$-free graphs Maria Chudnovsky, and Rose McCarty (Princeton University); Marcin Pilipczuk, and Michał Pilipczuk (University of Warsaw); Paweł Rzążewski (Warsaw University of Technology)
Poly-logarithmic Competitiveness for the $k$-Taxi Problem Anupam Gupta (Carnegie Mellon); Amit Kumar (IIT Delhi); Debmalya Panigrahi (Duke University)
Revenue Maximization for Buyers with Costly Participation Yannai A. Gonczarowski (Harvard University); Nicole Immorlica (Microsoft Research); Yingkai Li (Yale University); Brendan Lucier (Microsoft Research)
Faster Rectangular Matrix Multiplication by Combination Loss Analysis François Le Gall (Nagoya University)
Convex Minimization with Integer Minima in $widetilde O(n^4)$ Time Haotian Jiang (Microsoft Research); Yin Tat Lee (University Washington and Microsoft Research); Zhao Song (Adobe Research); Lichen Zhang (Massachusetts Institute of Technology)
Parameterized algorithms for block-structured integer programs with large entries Jana Cslovjecsek (EPFL, Lausanne); Martin Koutecký (Charles University, Prague); Alexandra Lassota (Max Planck Institute for Informatics, Saarbrücken); Michał Pilipczuk (University of Warsaw); Adam Polak (Max Planck Institute for Informatics, Saarbrücken)
A polynomial-time $text{OPT}^eps$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph Jana Cslovjecsek (EPFL); Michał Pilipczuk (University of Warsaw); Karol Węgrzycki (Saarland University and Max Planck Institute for Informatics)
The Time Complexity of Fully Sparse Matrix Multiplication Amir Abboud (Weizmann Institute of Science); Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Nick Fischer (Weizmann Institute of Science); Marvin Künnemann (RPTU Kaiserslautern-Landau)
Determinantal Sieving Eduard Eiben (Royal Holloway, University of London); Tomohiro Koana (Technische Universität Berlin); Magnus Wahlström (Royal Holloway, University of London)
Equilibrium Dynamics in Market Games with Exchangeable and Divisible Resources Jose Correa (Universidad de Chile); Tobias Harks (University of Passau); Anja Schedel (Passau University); José Verschae (Pontificia Universidad Católica de Chile)
Edge-disjoint paths in expanders: online with removals Nemanja Draganic (ETH Zurich); Rajko Nenadov (University of Auckland)
Smoothed Complexity of SWAP in Local Graph Partitioning Xi Chen (Columbia University); Chenghao Guo (Massachusetts Institute of Technology); Emmanouil-Vasileios Vlatakis-Gkaragkounis (UC Berkeley); Mihalis Yannakakis (Columbia University)
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas Xi Chen (Columbia University); Anindya De (University of Pennsylvania); Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio (Columbia University)
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable Sayan Bandyapadhyay (Portland State University); William Lochet (CNRS, LIRMM); Daniel Lokshtanov (University of California Santa Barbara, USA); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai)
Gap Amplification for Reconfiguration Problems Naoto Ohsaka (CyberAgent, Inc.)
Learning Hard-Constrained Models with One Sample Andreas Galanis (University of Oxford); Alkis Kalavasis (National Technical University of Athens); Anthimos Vardis Kandiros (Massachusetts Institute of Technology)
Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary Jan van den Brand, and Anastasiia Alokhina (Georgia Tech)
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory Arun Jambulapati, and Victor Reis (University of Washington); Kevin Tian (Microsoft Research)
Adaptive Out-Orientations with Applications Chandra Chekuri (University of Illinois at Urbana-Champaign); Aleksander Bjørn Grodt Christiansen (Technical University of Denmark, DTU); Jacob Holm (University of Copenhagen); Ivor van der Hoog (Technical University of Denmark, DTU); Kent Quanrud (Purdue University); Eva Rotenberg (Technical University of Denmark, DTU); Chris Schwiegelshohn (Aarhus University)
The Effect of Sparsity on k-Dominating Set and Related First-Order Graph Properties Nick Fischer (Weizmann Institute of Science); Marvin Künnemann, and Mirza Redzic (Rheinland-Pfälzische Technische Universität Kaiserslautern-Landau, Germany)
Untangling Graphs on Surfaces Éric Colin de Verdière (LIGM, CNRS, Univ Gustave Eiffel, Marne-la-Vallée); Vincent Despré (Université de Lorraine, CNRS, Inria, LORIA, Nancy); Loïc Dubois (LIGM, Univ Gustave Eiffel, CNRS, Marne-la-Vallée)
Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model Itai Dinur (Ben-Gurion University)
*Fast 2-Approximate All-Pairs Shortest Paths Michal Dory (University of Haifa); Sebastian Forster (University of Salzburg); Yael Kirkpatrick (Massachusetts Institute of Technology); Yasamin Nazari (VU Amsterdam); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Tijn de Vos (University of Salzburg)
Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth Arpit Agarwal (Columbia University); Sanjeev Khanna, Huan Li, and Prathamesh Patil (University of Pennsylvania); Chen Wang (Rutgers University); Nathan White (University of Pennsylvania); Peilin Zhong (Google Research)
An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism Timothy M. Chan (UIUC); Pingan Cheng (Aarhus University); Da Wei Zheng (UIUC)
On (1+eps)-Approximate Flow Sparsifiers Yu Chen (EPFL); Zihan Tan (Rutgers University)
A PTAS for $ell_0$-Low Rank Approximation: Solving Dense CSPs over Reals Vincent Cohen-Addad (Google Research, France); Chenglin Fan (Pennsylvania State University); Suprovat Ghoshal (Northwestern University & TTIC); Euiwoong Lee (University of Michigan); Arnaud de Mesmay (CNRS, LIGM, Université Gustave Eiffel); Alantha Newman (Université Grenoble Alpes); Tony Chang Wang (University of Wisconsin, Madison)
Adversarial Low Degree Testing Dor Minzer, and Kai Zhe Zheng (Massachusetts Institute of Technology)
Single-Source Unsplittable Flows in Planar Graphs Vera Traub (University of Bonn); Laura Vargas Koch, and Rico Zenklusen (ETH Zurich)
Deterministic Byzantine Agreement with Adaptive O(nf) Communication Fatima Elsheimy (Yale University); Giorgos Tsimos (University of Maryland, College Park); Charalampos Papamanthou (Yale University)
Sublinear Time Low-Rank Approximation of Toeplitz Matrices Kshiteej Sheth (EPFL, Switzerland); Cameron Musco (University of Massachusetts Amherst)
Sparse Regular Expression Matching Philip Bille, and Inge Li Gørtz (DTU Compute)
Controlling Tail Risk in Online Ski-Rental Michael Dinitz (Johns Hopkins University); Sungjin Im (University of California Merced); Thomas Lavastida (University of Texas at Dallas); Benjamin Moseley (Carnegie Mellon University); Sergei Vassilvitskii (Google)
School Redistricting: Wiping Unfairness Off the Map Ariel Procaccia, Isaac Robinson, and Jamie Tucker-Foltz (Harvard University)
Robust Sparsification for Matroid Intersection with Applications Chien-Chung Huang (CNRS, DI ENS, PSL); François Sellier (Université Paris Cité, CNRS, IRIF and Mines Paris, PSL)
Breaking the 3/4 Barrier for Approximate Maximin Share Hannaneh Akrami (Max Planck Institute for Informatics, Graduate school of Saarland University); Jugal Garg (University of Illinois at Urbana-Champaign)
Triangulations Admit Dominating Sets of Size 2n/7 Aleksander Bjørn Grodt Christiansen, Eva Rotenberg, and Daniel Rutschmann (Technical University of Denmark, DTU)
Solving Frechet Distance Problems by Algebraic Geometric Methods Siu-Wing Cheng, and Haoqiang Huang (HKUST)
On the hardness of finding balanced independent sets in random bipartite graphs Will Perkins, and Yuzhou Wang (Georgia Tech)
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time Sayan Bhattacharya, and Martin Costa (University of Warwick); Nadav Panski, and Shay Solomon (Tel Aviv University)
Prior-Independent Auctions for Heterogeneous Bidders Guru Guruganesh (Google Research); Aranyak Mehta, and Di Wang (Google); Kangning Wang (Stanford University)
A Unifying Framework for Differentially Private Sums under Continual Observation Monika Henzinger (IST-Austria); Jalaj Upadhyay (Rutgers University); Sarvagya Upadhyay (Fujitsu Laboratories of America)
On Dynamic Graph Algorithms with Predictions Jan van den Brand (Georgia Tech); Sebastian Forster (University of Salzburg); Yasamin Nazari (VU Amsterdam); Adam Polak (Max Planck Institute for Informatics, Saarbrücken)
Improved Approximations for Ultrametric Violation Distance Moses Charikar, and Ruiquan Gao (Stanford University)
Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem Nick Fischer (Weizmann Institute of Science)
Improving the competitive ratio of collaborative tree exploration with tree-mining Romain Cosson (Inria)
Fast and Accurate Approximations of the Optimal Transport in Semi-Continuous and Discrete Settings Pankaj K Agarwal (Duke University); Sharath Raghvendra, and Pouyan Shirzadian (Virginia Tech); Keegan Yao (Duke University)
Fast Fourier transform via automorphism groups of rational function fields Songsong Li, and Chaoping Xing (Shanghai Jiao Tong University)
Quotient sparsification for submodular functions Kent Quanrud (Purdue University)
Maintaining Matroid Intersections Online Niv Buchbinder (Tel Aviv University); Anupam Gupta (Carnegie Mellon); Daniel Hathcock (Carnegie Mellon University); Anna Karlin (University of Washington); Sherry Sarkar (Carnegie Mellon University)
Santa Claus meets Makespan and Matroids: Algorithms and Reductions Etienne Bamas (ETHZ); Alexander Lindermayr, and Nicole Megow (University of Bremen); Lars Rohwedder (Maastricht University); Jens Schlöter (University of Bremen)
Strongly Polynomial Frame Scaling to High Precision Akshay Ramachandran (CWI Amsterdam, University of Amsterdam); Daniel Dadush (CWI Amsterdam)
Exact Community Recovery in the Geometric SBM Julia Gaudio, Xiaochun Niu, and Ermin Wei (Northwestern University)
Nearly Optimal Approximate Dual-Failure Replacement Paths Shiri Chechik (Tel-Aviv University); Tianyi Zhang (Tel Aviv University)
Faster Sublinear-Time Edit Distance Karl Bringmann, and Alejandro Cassis (Saarland University and Max Planck Institute for Informatics); Nick Fischer (Weizmann Institute of Science); Tomasz Kociumaka (Max Planck Institute for Informatics)
Adjacency Sketches in Adversarial Environments Moni Naor, and Eugene Pekel (Weizmann Institue of Science)
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation Raphael A. Meyer (New York University); Cameron Musco (University of Massachusetts Amherst); Christopher Musco (New York University)
A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluation Moses Charikar (Stanford University); Michael Kapralov (EPFL); Erik Waingarten (University of Pennsylvania)
Optimal rates for ranking a permuted isotonic matrix in polynomial time Emmanuel Pilliat (IMAG, CNRS, Univ. Montpellier); Alexandra Carpentier (Institut für Mathematik, Universität Potsdam.); Nicolas Verzelen (MISTEA, INRAE, Univ. Montpellier)
Fast Sampling of b-Matchings and b-Edge Covers Zongchen Chen, and Yuzhou Gu (Massachusetts Institute of Technology)
Shortest Disjoint Paths on a Grid Mathieu Mari (University of Warsaw and IDEAS NCBR); Anish Mukherjee (University of Warwick); Piotr Sankowski (University of Warsaw and IDEAS NCBR)
On Deterministically Approximating Total Variation Distance Weiming Feng (University of Edinburgh); Liqiang Liu, and Tianren Liu (Peking University)
The Grid-Minor Theorem Revisited Vida Dujmovic (University of Ottawa); Robert Hickingbotham (Monash University); Jędrzej Hodor (Jagiellonian University); Gwenaël Joret (Université libre de Bruxelles); Hoang La, and Piotr Micek (Jagiellonian University); Pat Morin (Carleton University); Clément Rambaud (PSL University); David Wood (Monash University)
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model Diptarka Chakraborty (National University of Singapore); Sourav Chakraborty (ISI Kolkata); Gunjan Kumar (National University of Singapore)
How to Pierce Many Simplices in a Higher-Dimensional Hypergraph Natan Rubin (Ben-Gurion University)
Integer Programming with GCD Constraints Rémy Défossez (IMDEA Software Institute, Spain & École normale supérieure, France); Christoph Haase (University of Oxford, UK); Alessio Mansutti (IMDEA Software Institute, Spain); Guillermo A. Pérez (University of Antwerp, Flanders Make, Belgium)
*Faster Approximate All Pairs Shortest Paths Barna Saha, and Christopher Ye (University of California San Diego)
**Combinatorial Contracts Beyond Gross Substitutes Yoav Gal Tzur, and Michal Feldman (Tel Aviv University); Paul Duetting (Google Research)
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition Tuukka Korhonen (University of Bergen); Daniel Lokshtanov (University of California Santa Barbara, USA)
An Improved Classical Singular Value Transformation for Quantum Machine Learning Ainesh Bakshi (MIT); Ewin Tang (University of Washington)
Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations Barış Can Esmer (CISPA Helmholtz Center for Information Security); Ariel Kulik (Technion); Dániel Marx (CISPA Helmholtz Center for Information Security); Daniel Neuen (University of Bremen); Roohani Sharma (Max Planck Institute for Informatics)
Exact Shortest Paths with Rational Weights on the Word RAM Adam Karczmarz (University of Warsaw and IDEAS NCBR); Wojciech Nadara, and Marek Sokołowski (University of Warsaw)
Uniformity Testing over Hypergrids with Subcube Conditioning Cassandra Marcussen (Harvard University); Xi Chen (Columbia University)
An $tildeOmega(sqrt{log |T|})$ Lower Bound for Steiner Point Removal Yu Chen (EPFL); Zihan Tan (Rutgers University)
Oracle Efficient Online Multicalibration and Omniprediction Sumegha Garg, Christopher Jung, and Omer Reingold (Stanford University); Aaron Roth (University of Pennsylvania)
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets Omar Alrabiah, Venkatesan Guruswami, and Ray Li (UC Berkeley)
Fault-Tolerant Spanners against Bounded-Degree Edge Failures Greg Bodwin (University of Michigan); Bernhard Haeupler (ETH Zurich & CMU); Merav Parter (Weizmann)
Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms Chandra Sekhar Mukherjee, and Jiapeng Zhang (University of Southern California)
New Approximation Bounds for Small-Set Vertex Expansion Suprovat Ghoshal (Northwestern University, TTIC); Anand Louis (Indian Institute of Science, Bangalore)
Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems Zongchen Chen (MIT)
Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time David Harris (University of Maryland)
A Faster Combinatorial Algorithm for Maximum Bipartite Matching Julia Chuzhoy (Toyota Technological Institute at Chicago); Sanjeev Khanna (University of Pennsylvania)
The Minority Dynamics and the Power of Synchronicity Luca Becchetti (Sapienza University of Rome, Rome, Italy); Andrea Clementi, and Francesco Pasquale (Tor Vergata University of Rome, Rome, Italy); Luca Trevisan (Bocconi University of Milan, Milan, Italy); Robin Vacus (CNRS, IRIF, Paris, France); Isabella Ziccardi (Bocconi University of Milan, Milan, Italy)
New Explicit Constant-Degree Lossless Expanders Louis Golowich (University of California at Berkeley)
Max-s,t-Flow Oracles and Negative Cycle Detection in Planar Digraphs Adam Karczmarz (University of Warsaw and IDEAS NCBR)
New Bounds for Matrix Multiplication: from Alpha to Omega Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu (Massachusetts Institute of Technology); Renfei Zhou (Tsinghua University)
New SDP Roundings and Certifiable Approximation for Cubic Optimization Jun-Ting Hsieh, and Pravesh Kothari (CMU); Lucas Pesenti, and Luca Trevisan (Bocconi University)
Delaunay Bifiltrations of Functions on Point Clouds Ángel Javier Alonso, and Michael Kerber (Graz University of Technology); Tung Lam, and Michael Lesnick (University at Albany, SUNY)
Dynamic Dictionary with Subconstant Wasted Bits per Key Tianxiao Li, and Jingxun Liang (IIIS, Tsinghua University); Huacheng Yu (Princeton University); Renfei Zhou (IIIS, Tsinghua University)
Cactus Representation of Minimum Cuts: Derandomize and Speed up Zhongtian He (Princeton University); Shang-En Huang (Boston College); Thatchaphol Saranurak (University of Michigan)
Set Covering with Our Eyes Wide Shut Anupam Gupta (Carnegie Mellon); Gregory Kehne (Harvard University); Roie Levin (Tel Aviv University)
How Many Neurons Does it Take to Approximate the Maximum? Itay Safran (Purdue University); Daniel Reichman (Worcester Polytechnic Institute); Paul Valiant (Purdue University)
Odd Cycle Transversal on $P_5$-free Graphs in Quasi-polynomial Time Akanksha Agrawal (IIT Madras); Paloma T. Lima (IT University of Copenhagen); Daniel Lokshtanov (UCSB); Saket Saurabh (IMSc); Roohani Sharma (Max Planck Institute for Informatics)
Optimal Bounds on Private Graph Approximation Jingcheng Liu (Nanjing University); Jalaj Upadhyay (Rutgers University); Zongrui Zou (Nanjing University)
Tree Containment Above Minimum Degree is FPT Fedor V. Fomin, and Petr A. Golovach (Department of Informatics, University of Bergen, Norway); Danil Sagunov (St. Petersburg Department of V.A. Steklov Institute of Mathematics, Russia); Kirill Simonov (Hasso Plattner Institute, University of Potsdam, Germany)
Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation Maximilian Gläser, and Marc E. Pfetsch (TU Darmstadt)
Positivity certificates for linear recurrences Alaa Ibrahim, and Bruno Salvy (Inria)
Online Robust Mean Estimation Sihan Liu (UCSD); Daniel M. Kane (University of California, San Diego); Hanshen Xiao (Massachusetts Institute of Technology); Ilias Diakonikolas (UW Madison)
VC Set Systems in Minor-free (Di)Graphs and Applications Hung Le (UMass Amherst); Christian Wulff-Nilsen (University of Copenhagen)
A Parameterized Family of Meta-Submodular Functions Mehrdad Ghadiri (Georgia Institute of Technology); Richard Santiago (ETH Zurich); Bruce Shepherd (University of British Columbia)
Faster exact and approximation algorithms for packing and covering matroids via push-relabel Kent Quanrud (Purdue University)
Learning Prophet Inequality and Pandora’s Box with Limited Feedback Khashayar Gatmiry (MIT); Thomas Kesselheim (University of Bonn); Sahil Singla (Georgia Tech); Yifan Wang (Georgia Institute of Technology)
Impossibilities for Obviously Strategy-Proof Mechanisms Shiri Ron (Weizmann Institute of Science)
Cliquewidth and Dimension Gwenaël Joret (Université libre de Bruxelles); Piotr Micek (Jagiellonian University); Michał Pilipczuk (University of Warsaw); Bartosz Walczak (Jagiellonian University)
A $(3+epsilon)$-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds Moritz Buchem, Katja Ettmayr, Hugo Kooki Kasuya Rosado, and Andreas Wiese (Technical University of Munich)
Shannon meets Gray: Noise-robust, Low-sensitivity Codes with Applications in Differential Privacy David Rasmussen Lolck, and Rasmus Pagh (University of Copenhagen)
Simpler and Higher Lower Bounds for Shortcut Sets Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu (MIT)
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data Rajat De, and Dominik Kempa (Stony Brook University)
Dynamic algorithms for $k$-center on graphs Emilio Cruciani, and Sebastian Forster (University of Salzburg); Gramoz Goranci (University of Vienna); Yasamin Nazari (VU Amsterdam); Antonis Skarlatos (University of Salzburg)
Deterministic Near-Linear Time Minimum Cut in Weighted Graphs Monika Henzinger (Universitaet Wien); Jason Li, and Satish Rao (UC Berkeley); Di Wang (Google)
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank Nathaniel Harms (EPFL); Viktor Zamaraev (University of Liverpool, UK)
Fully Dynamic Consistent $k$-Center Clustering Christoph Grunau (ETH Zurich); Bernhard Haeupler (ETH Zurich & CMU); Rajesh Jayaram (Google); Jakub Łącki (Google Research, New York); Václav Rozhoň (ETH Zurich)
Higher-Order Cheeger Inequality for Partitioning with Buffers Konstantin Makarychev (Northwestern University); Yury Makarychev (TTIC); Liren Shan, and Aravindan Vijayaraghavan (Northwestern University)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems Vahid R. Asadi (University of Waterloo); Alexander Golovnev (Georgetown University); Tom Gur (University of Cambridge); Igor Shinkar (Simon Fraser University); Sathyawageeswar Subramanian (University of Warwick)
Fast Approximation Algorithms for Piercing Boxes by Points Pankaj K. Agarwal (Duke University); Sariel Har-Peled (University of Illinois at Urbana-Champaign); Rahul Raychaudhury (Duke University); Stavros Sintos (University of Illinois at Chicago)
New Efficient Black Box Polynomial Root-finders Victor Pan (CUNY)
Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs Yi-Jun Chang (National University of Singapore); Da Wei Zheng (University of Illinois Urbana-Champaign)
2-Approximation for Prize-Collecting Steiner Forest Ali Ahmadi, Iman Gholami, Mohammad Taghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi (University of Maryland)
Computations with Polynomial Evaluation Oracle: Ruling Out Superlinear SETH-based Lower Bounds Tatiana Belova, and Alexander Kulikov (Steklov Institute of Mathematics at St. Petersburg); Ivan Mihajlin (JetBrains Research); Grigory Reznikov (Steklov Institute of Mathematics at St. Petersburg); Olga Ratseeva, and Denil Sharipov (St. Petersburg State University)
A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions Yair Carmon (Tel Aviv University); Arun Jambulapati (University of Washington); Yujia Jin, and Aaron Sidford (Stanford University)
Fully Dynamic Min-Cut in Subpolynomial Time Wenyu Jin, and Xiaorui Sun (University of Illinois at Chicago); Mikkel Thorup (University of Copenhagen)
Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints Varun Suriyanarayana (Cornell University); Varun Sivashankar, and Siddharth Gollapudi (Microsoft Research); David Shmoys (Cornell University)
Count on CFI graphs for #P-hardness Radu Curticapean (IT University of Copenhagen and University of Regensburg)
Computing the 5-edge-connected components in linear time Evangelos Kosinas (University of Ioannina)
On the Hardness of PosSLP Peter Buergisser (TU Berlin); Gorav Jindal (Max Planck Institute for Software Systems)
Power of Posted-price Mechanisms for Prophet Inequalities Kiarash Banihashem, and Mohammad Taghi Hajiaghayi (University of Maryland); Dariusz Kowalski (Augusta University, Augusta, Georgia); Piotr Krysta (University of Liverpool); Jan Olkowski (Uniwersytet Warszawski, Warszawa, Poland)
Conflict Checkable and Decodable Codes and Their Applications Benny Applebaum, and Eliran Kachlon (Tel Aviv University)
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits Mrinal Kumar, Varun Ramanathan, and Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai)
Sorting and Selection in Rounds with Adversarial Comparisons Christopher Trevisan (University of Waterloo)
Robust 1-bit Compressed Sensing with Iterative Hard Thresholding Namiko Matsumoto (UC San Diego); Arya Mazumdar (University of California San Diego)
Fast Algorithms for Structured Linear Programs Sally Dong (University of Washington); Gramoz Goranci (University of Vienna); Lawrence Li, and Sushant Sachdeva (University of Toronto); Guanghao Ye (Massachusetts Institute of Technology)
Arborescences, Colorful Forests, and Popularity Telikepalli Kavitha (TIFR, Mumbai); Kazuhisa Makino (Kyoto University); Ildikó Schlotter (Centre for Economic and Regional Studies); Yu Yokoi (Tokyo Institute of Technology)
Dynamic Algorithms for Matroid Submodular Maximization Kiarash Banihashem (University of Maryland); Leyla Biabani (Eindhoven University of Technology); Samira Goudarzi, Mohammad Taghi Hajiaghayi, and Peyman Jabbarzade (University of Maryland); Morteza Monemizadeh (Eindhoven University of Technology)
Partial coloring complex, vertex decomposability and Tverberg’s theorem with constraints Sharareh Alipour (Tehran Institute for Advanced Studies, Khatam University); Amir Jafari, Mohammad Hassan Mazidi, and Seyed Abolfazl Najafian (Sharif University of Technology, Department of Mathematical Sciences)
Factoring Pattern-Free Permutations into Separable ones Édouard Bonnet (CNRS); Romain Bourneuf (ENS de Lyon); Colin Geniet, and Stephan Thomasse (ENS Lyon)
The Hierarchy of Hereditary Sorting Operators Vít Jelínek (Charles University, Prague); Michal Opler (Czech Technical University, Prague); Jakub Pekárek (Charles University, Prague)
A TIGHT BOUND FOR TESTING PARTITION PROPERTIES Asaf Shapira (Tel Aviv University); Henrique Stagni (University of Sao Paolo)
Edge-weighted Online Stochastic Matching: Beating $1-frac1e$ Shuyi Yan (University of Copenhagen)
Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation Dmitriy Kunisky (Yale University)
Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses Nima Anari (Stanford University); Vishesh Jain (University of Illinois Chicago); Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong (Stanford University)
A (3 + ε)-Approximate Correlation Clustering Algorithm in Dynamic Streams Mélanie Cambus (Aalto university); Fabian Kuhn (University of Freiburg); Etna Lindy, Shreyas Pai, and Jara Uitto (Aalto University)
Online duet between Metric Embeddings and Minimum-Weight Perfect Matchings Sujoy Bhore (Indian Institute of Technology Bombay); Arnold Filtser (Bar Ilan University); Csaba D. Toth (California State University Northridge)
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results Lin Chen (Texas Tech University); Jiayi Lian, Yuchen Mao, and Guochuan Zhang (Zhejiang University)
Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs Adam Brown, and Aditi Laddha (Georgia Institute of Technology); Madhusudhan Reddy Pittu (Carnegie Mellon University); Mohit Singh (Georgia Institute of Technology)
Meta-theorems for Parameterized Streaming Algorithms Daniel Lokshtanov (University of California, Santa Barbara); Pranabendu Misra (Chennai Mathematical Institute); Fahad Panolan (Indian Institute of Technology, Hyderabad); M. S. Ramanujan (University of Warwick); Saket Saurabh (The Institute of Mathematical Sciences, HBNI and University of Bergen); Meirav Zehavi (Ben-Gurion University)
A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching Taisuke Izumi, Naoki Kitamura, and Yutaro Yamaguchi (Osaka University)
Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment Pankaj K. Agarwal (Duke University); Dan Halperin, and Micha Sharir (Tel Aviv University); Alex Steiger (Duke University)
Simple Delegated Choice Ali Khodabakhsh (University of Texas, Austin); Emmanouil Pountourakis (Drexel University); Sam Taggart (Oberlin)
Combinatorial Stationary Prophet Inequalities Neel Patel (University of Southern California); David Wajc (Technion – Israel Institute of Technology)
Dynamic Dynamic Time Warping Karl Bringmann (Saarland University and Max Planck Institute for Informatics); Nick Fischer (Weizmann Institute of Science); Ivor van der Hoog (Technical University of Denmark); Evangelos Kipouridis (Saarland University and Max Planck Institute for Informatics); Tomasz Kociumaka (Max Planck Institute for Informatics); Eva Rotenberg (Technical University of Denmark, DTU)
**On Supermodular Contracts and Dense Subgraphs Shaddin Dughmi, Neel Bharatkumar Patel, Aditya Prasad, and Ram Deo-Campo Vuong (University of Southern California)
Tight approximability for MAX 2-SAT and its relatives, under UGC Joshua Brakensiek (Stanford University); Neng Huang (University of Chicago); Uri Zwick (Tel Aviv University)
Lower Bound for Two-pass Streaming Algorithms for Maximum Matching Approximation Christian Konrad, and Kheeran Naidu (University of Bristol)
Random Matrix Perturbation: Davis-Kahan for the Infinity Norm I Abhinav Bhardwaj, and Van Vu (Yale University)
Minimization is Harder in the Prophet World Vasilis Livanos, and Ruta Mehta (University of Illinois Urbana-Champaign)
Fully Dynamic Matching: $(2-sqrt{2})$-Approximation in Polylog Update Time Amir Azarmehr, and Soheil Behnezhad (Northeastern University); Mohammad Roghani (Stanford University)
Distances and shortest paths on graphs of bounded highway dimension: Simple, Fast, Dynamic Sébastien Collette (Synapsis Group); John Iacono (Université Libre de Bruxelles and Synapsis Group)
Representative set statements for delta-matroids and the Mader delta-matroid Magnus Wahlström (Royal Holloway, University of London)
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More Hsien-Chih Chang, and Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts); Lazar Milenković, and Shay Solomon (Tel Aviv University); Cuong Than (University of Massachusetts Amherst)