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 $\tilde\Omega(\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)