Accepted Papers

This list is provided for reference until the online program becomes available. Title and author information appears as originally submitted; updates 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.

Renyi-infinity constrained sampling with d^3 membership queries

Yunbum Kook (Georgia Institute of Technology); Matthew S. Zhang (University of Toronto)

Lipschitz Continuous Algorithms for Covering Problems    

Soh Kumabe (CyberAgent); Yuichi Yoshida (National Institute of Informatics)

Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups

Ruiwen Dong (Saarland University)

Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes

Mook Kwon Jung, Seokyun Kang, Hee-Kap Ahn (POSTECH)

Near-Optimal Quantum Algorithms for Approximate Pattern Matching

Tomasz Kociumaka (Max Planck Institute for Informatics); Jakob Nogler (ETH Zurich); Philip Wellnitz (National Institute of Informatics)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut

Raghuvansh R. Saxena (TIFR); Noah Singer (Carnegie Mellon University); Madhu Sudan (Harvard); Santhoshini Velusamy (Toyota Technological Institute at Chicago)

Inapproximability of Maximum Diameter Clustering for Few Clusters

Ashwin Padaki (Columbia University); Henry Fleischmann (University of Michigan); Karthik C. S. (Rutgers University); Kyrylo Karlov (Charles University); Stepan Zharkov (Stanford University)

Approximately Counting Knapsack Solutions in Subquadratic Time

Weiming Feng (ETH Zurich); Ce Jin (MIT)

A Fast Algorithm for Computing Zigzag Representatives

Tamal K. Dey (Department of Computer Science, Purdue University); Tao Hou (Department of 
Computer Science, University of Oregon); Dmitriy Morozov (Lawrence Berkeley National Laboratory)

Potential Hessian Ascent: The Sherrington-Kirkpatrick Model

Juspreet Singh Sandhu (University of California, Santa Cruz); David Jekel (University of Copenhagen, Denmark); Jonathan Shi (University of California San Diego)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching

Nick Fischer (INSAIT, University of Sofia "St. Kliment Ohridski”); Ce Jin, Yinzhan Xu (MIT)

Competitive strategies to use "warm start" algorithms with predictions

Avrim Blum (Toyota Technological Institute at Chicago); Vaidehi Srinivas (Northwestern University)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs

Simon Doring (Max Planck Institute for Informatics); Daniel Marx (CISPA Helmholtz Center for Information Security); Philip Wellnitz (National Institute of Informatics)

Partitioning a Polygon Into Small Pieces

Mikkel Abrahamsen, Nichlas Langhoff Rasmussen (University of Copenhagen)

Computing the second and third systoles of a combinatorial surface

Matthijs Ebbens (University of Cologne); Francis Lazarus (Universite Grenoble Alpes)

A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization

Shuchi Chawla (UT Austin); Dimitrios Christou (University of Texas at Austin); Trung Dang (UT Austin); Zhiyi Huang (University of Texas at Austin); Gregory Kehne (Washington University in St. Louis); Rojin Rezvan (University of Texas at Austin)

Hiring for An Uncertain Task: Joint Design of Information and Contracts

Matteo Castiglioni (Politecnico di Milano); Junjie Chen (City University of Hong Kong)

An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition

Pascal Koiran (Ecole Normale Superieure de Lyon)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Sepehr Assadi (University of Waterloo); Sanjeev Khanna (University of Pennsylvania); Peter Kiss (University of Warwick)

Private Mean Estimation with Person-Level Differential Privacy

Sushant Agarwal (Northeastern University); Gautam Kamath (University of Waterloo); Mahbod Majid (Carnegie Mellon University); Argyris Mouzakis (University of Waterloo); Rose Silver, Jonathan Ullman (Northeastern University)

Testing Approximate Stationarity Concepts for Piecewise Affine Functions

Lai Tian, Anthony Man-Cho So (The Chinese University of Hong Kong)

Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees

Swati Gupta (MIT); Jai Moondra, Mohit Singh (Georgia Tech)

A Lower Bound for Light Spanners in General Graphs

Greg Bodwin, Jeremy Flics (University of Michigan)

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

Erik Waingarten (University of Pennsylvania); Moses Charikar (Stanford University)

A topological proof of the Hell-Nesetril dichotomy

Sebastian Meyer (TU Dresden, Germany); Jakub Oprsal (University of Birmingham, UK)

A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints

Jesper Nederlof (Utrecht University); Celine Swennenhuis (Eindhoven University of Technology); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics)

Maximum Span Hypothesis: A Weaker Assumption than Gap-ETH for Parameterized Complexity

Karthik C. S. (Rutgers University); Subhash Khot (NYU)

Massively Parallel Minimum Spanning Tree in General Metric Spaces

Amir Azarmehr, Soheil Behnezhad (Northeastern University); Rajesh Jayaram, Jakub Lacki, Vahab Mirrokni, Peilin Zhong (Google Research)

Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions

Jane Lange (MIT); Ephraim Linder, Sofya Raskhodnikova (Boston University); Arsen Vasilyan (MIT)

An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs

Natan Rubin (Ben Gurion University)

A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design

Matteo Castiglioni (Politecnico di Milano); Junjie Chen, Minming Li (City University of Hong Kong); Haifeng Xu (University of Chicago, Google Research); Song Zuo (Google Research)

New Separations and Reductions for Directed Hopsets and Preservers

Gary Hoppenworth (University of Michigan); Yinzhan Xu, Zixuan Xu (MIT)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity

Tijn de Vos (University of Salzburg); Aleksander Bjorn Grodt Christiansen (Technical University of Denmark, DTU)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes

Ignasi Sau (LIRMM, Univ Montpellier, CNRS, Montpellier, France); Giannοs Stamoulis (Institute of Informatics, University of Warsaw, Poland); Dimitrios M. Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies

Yaowei Long, Seth Pettie, Thatchaphol Saranurak (University of Michigan)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local

Merav Parter, Asaf Petruschka, Shay Sapir, Elad Tzailk (Weizmann Institute)

Approximating Traveling Salesman Problems Using a Bridge Lemma

Martin Bohm (University of Wroclaw); Zachary Friggstad (University of Alberta); Tobias Momke (University of Augsburg); Joachim Spoerhase (University of Liverpool, United Kingdom)

Top-k Document Retrieval in Compressed Space

Gonzalo Navarro (University of Chile); Yakov Nekrich (Michigan Technological University)

Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares

Hongjie Chen, S Deepak Narayanan, David Steurer (ETH Zurich)

A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs

Daniel Paul-Pena, C. Seshadhri (University of California, Santa Cruz)

Universal Perfect Samplers for Incremental Streams

Seth Pettie, Dingyu Wang (University of Michigan)

Losing Treewidth In The Presence Of Weights

Michal Wlodarczyk (University of Warsaw)

Embedding Planar Graphs into Graphs of Treewidth O(log^3 n)

Hsien-Chih Chang (Dartmouth College); Vincent Cohen-Addad (Google Research); Jonathan Conroy (Dartmouth College); Hung Le (University of Massachusetts Amherst); Marcin Pilipczuk, Michal Pilipczuk (University of Warsaw, Poland)

Multi-Agent Combinatorial Contracts

Paul Duetting (Google); Tomer Ezra (Harvard); Thomas Kesselheim (University of Bonn); Michal Feldman (Tel Aviv University)

Improving the Leading Constant of Matrix Multiplication

Hantao Yu, Josh Alman (Columbia University)

Min-CSPs on Complete Instances

Aditya Anand, Euiwoong Lee, Amatya Sharma (University of Michigan - Ann Arbor)

Tight Streaming Lower Bounds for Deterministic Approximate Counting

Yichuan Wang (Tsinghua University)

Low Degree Local Correction Over the Boolean Cube

Prashanth Amireddy (Harvard University); Amik Raj Behera (Aarhus University); Manaswi Paraashar, Srikanth Srinivasan (University of Copenhagen); Madhu Sudan (Harvard University)

Lift-and-Project Integrality Gaps for Santa Claus

Etienne Bamas (ETH AI Center, Zurich, Switzerland)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

Aditya Anand, Thatchaphol Saranurak (University of Michigan); Yunfan Wang (Tsinghua University, IIIS)

Forall-exist statements in pseudopolynomial time

Friedrich Eisenbrand, Eleonore Bach (EPFL); Robert Weismantel (ETH Zurich); Thomas Rothvoss (University of Washington)

Faster Vizing and Near-Vizing Edge Coloring Algorithms

Sepehr Assadi (University of Waterloo)

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Aaron Bernstein (Rutgers University); Jiale Chen (Stanford University); Aditi Dudeja (University of Salzburg); Zachary Langley (Rutgers University); Aaron Sidford, Ta-Wei Tu (Stanford University)

Finding irrelevant vertices in linear time on bounded-genus graphs

Petr A. Golovach (University of Bergen); Stavros G. Kolliopoulos (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Giannos Stamoulis (Institute of Informatics, University of Warsaw, Poland); Dimitrios Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France)

Quartic quantum speedups for planted inference

Alexander Schmidhuber (MIT, Google); Ryan O'Donnell (CMU); Robin Kothari, Ryan Babbush (Google)

Efficient d-ary Cuckoo Hashing at High Load Factors by Bubbling Up

William Kuszmaul, Michael Mitzenmacher (Harvard University)

Asynchronous 3-Majority Dynamics with Many Opinions

Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik (King's College London); Nobutaka Shimizu (Institute of Science Tokyo); Takeharu Shiraga (Chuo University)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more

Adam Karczmarz (University of Warsaw and IDEAS NCBR); Da Wei Zheng (University of Illinois at Urbana-Champaign)

Bounding epsilon-scatter dimension via metric sparsity

Romain Bourneuf (ENS de Lyon); Marcin Pilipczuk (University of Warsaw)

Almost Tight Bounds for Differentially Private Densest Subgraph

Michael Dinitz (Johns Hopkins University); Satyen Kale, Silvio Lattanzi, Sergei Vassilvitskii (Google Research)

On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions

Mete Seref Ahunbay, Martin Bichler (Technical University of Munich)

Relative-error monotonicity testing

Xi Chen (Columbia University); Anindya De (University of Pennsylvania); Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang (Columbia University)

Tree Independence Number IV. Even-hole-free Graphs

Maria Chudnovsky (Princeton University, USA); Peter Gartland (University of California at Santa Barbara); Sepehr Hajebi (University of Waterloo); Daniel Lokshtanov (University of California at Santa Barb); Sophie Spirkl (University of Waterloo)

Approximating Competitive Equilibrium by Nash Welfare

Jugal Garg (University of Illinois at Urbana Champaign); Yixin Tao (Shanghai University of Finance and Economics); Laszlo A. Vegh (Department of Mathematics, London School of Economics)

Fixed-Parameter Tractability of Hedge Cut

Fedor V. Fomin, Petr A. Golovach (University of Bergen); Tuukka Korhonen (University of Copenhagen); Daniel Lokshtanov (University of California, Santa Barbara); Saket Saurabh (IMSc)

Online Scheduling via Gradient Descent for Weighted Flow Time Minimization

Qingyun Chen, Sungjin Im, Aditya Petety (University of California, Merced, USA)

Spectral Independence Beyond Total Influence on Trees and Related Graphs

Xiaoyu Chen (Nanjing University); Xiongxin Yang (Northeast Normal University); Yitong Yin, Xinyuan Zhang (Nanjing University)

More Efficient Approximate k-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities.

Lucas Gretta (UC Berkeley); William He (Carnegie Mellon University); Angelos Pelecanos (UC Berkeley)

Sumsets, 3SUM, Subset Sum: Now for Real!

Nick Fischer (INSAIT, University of Sofia "St. Kliment Ohridski”)

Fast and Simple Sorting Using Partial Information

Bernhard Haeupler (INSAIT Bulgaria & ETH Zurich); Richard Hladik (ETH Zurich); John Iacono (Universite libre de Bruxelles); Vaclav Rozhon (INSAIT Bulgaria); Robert Tarjan (Princeton University); Jakub Tetek (University of Copenhagen)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers

Sujoy Bhore (IIT Bombay); Balazs Keszegh (Renyi institute); Andrey Kupavskii (CNRS); Hung Le (University of Massachusetts, Amherst, USA); Alexandre Louvet (Universite Sorbonne Paris Nord); Domotor Palvolgyi (ELTE); Csaba D. Toth (CSUN)

Embedding Probability Distributions into Low Dimensional ell_1: Tree Ising Models via Truncated Metrics

Moses Charikar, Spencer Compton, Chirag Pabbaraju (Stanford University)

Beyond 2-approximation for k-Center in Graphs

Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams (MIT); Nicole Wein (University of Michigan)

Complexity of polytope diameters via perfect matchings

Christian Nobel, Raphael Steiner (ETH Zurich)

Highway Dimension: a Metric View

Andreas Emil Feldmann (University of Sheffield); Arnold Filtser (Bar Ilan University)

Dynamic Consistent k-Center Clustering with Optimal Recourse

Antonis Skarlatos, Sebastian Forster (University of Salzburg)

Nearly Tight Bounds on Testing of Metric Properties

Yiqiao Bao, Sampath Kannan, Erik Waingarten (University of Pennsylvania)

Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits

Yuchen He, Zichun Ye, Chihao Zhang (Shanghai Jiao Tong University)

Improved List Size for Folded Reed-Solomon Codes

Shashank Srivastava (TTIC)

A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices

Seth Pettie (University of Michigan); Gabor Tardos (Renyi Institute, Budapest)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree

Charlie Carlson (UCSB); Xiaoyu Chen (Nanjing University); Weiming Feng (ETH Zurich); Eric Vigoda (University of California, Santa Barbara)

Constraint Satisfaction Problems with Advice

Suprovat Ghoshal (Northwestern University and TTIC); Konstantin Makarychev (Northwestern University); Yury Makarychev (TTIC)

Triply efficient shadow tomography

Robbie King (Caltech); David Gosset (University of Waterloo); Robin Kothari, Ryan Babbush (Google)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning

Michal Derezinski (University of Michigan); Christopher Musco (New York University); Jiaming Yang (University of Michigan, Ann Arbor)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition

Julia Chuzhoy (Toyota Technological Institute at Chicago); Merav Parter (Weizmann Institute of Science)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling

Mark Braverman (Princeton); Mahsa Derakhshan (Northeastern University); Tristan Pollner, Amin Saberi (Stanford University); David Wajc (Technion --- Israel Institute of Technology)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier

Anton Bukov, Shay Solomon, Tianyi Zhang (Tel Aviv University)

Mean-field Potts and random-cluster dynamics from high-entropy initializations

Antonio Blanca (Pennsylvania State University); Reza Gheissari (Northwestern University); Xusheng Zhang (Pennsylvania State University)

Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances

Yu Chen (EPFL); Zihan Tan (Rutgers University)

Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs

Feodor Dragan (Kent State University); Guillaume Ducoffe (National Institute for Research and Development in Informatics); Michel Habib (IRIF, Paris Diderot); Laurent Viennot (Inria, DI ENS)

Improved Differentially Private Continual Observation Using Group Algebra

Monika Henzinger (IST Austria); Jalaj Upadhyay (Rutgers)

A Tight (3/2 + epsilon)-Approximation Algorithm For Demand Strip Packing

Franziska Eberle (Technische Universitat Berlin); Felix Hommelsheim (Universitat Bremen); Malin Rau (Chalmers University of Technology); Stefan Walzer (Karlsruhe Institute of Technology)

More Asymmetry Yields Faster Matrix Multiplication

Josh Alman (Columbia University); Ran Duan (Tsinghua University); Virginia Vassilevska Williams (Massachusetts Institute of Technology); Yinzhan Xu, Zixuan Xu (MIT); Renfei Zhou (CMU)

The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms

Naren Sarayu Manoj, Max Ovsiankin (Toyota Technological Institute Chicago)

Crossing Number in Slightly Superexponential Time

Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (School of Computing, University of Leeds); Saket Saurabh (IMSc); Roohani Sharma (University of Bergen); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University of the Negev)

Clustering to Minimize Cluster-Aware Norm Objectives

Martin Herold (Max Planck Institute for Informatics, Saarland Informatics Campus); Joachim Spoerhase (University of Liverpool); Evangelos Kipouridis (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus)

Flip Dynamics for Sampling Colorings: Improving (11/6 - epsilon) Using A Simple Metric

Charlie Carlson, Eric Vigoda (UCSB)

On estimating the trace of quantum state powers

Yupan Liu (Nagoya University), Qisheng Wang (University of Edinburgh and Nagoya University)

Packing Short Cycles

Matthias Bentert, Fedor Fomin, Petr A. Golovach (University of Bergen); Tuukka Korhonen (University of Copenhagen); William Lochet (CNRS, LIRMM); Fahad Panolan (University of Leeds); M.S. Ramanujan (University of Warwick); Saket Saurabh (IMSc); Kirill Simonov (Hasso Plattner Institute, University of Potsdam)

Near-optimal hierarchical matrix approximation from matrix-vector products

Tyler Chen, Feyza Duman Keles (New York University); Diana Halikias (Cornell University); Cameron Musco (University of Massachusetts Amherst); Christopher Musco (New York University); David Persson (EPFL)

Lower Bounds for Convexity Testing

Xi Chen (Columbia University); Anindya De (University of Pennsylvania); Shivam Nadimpalli, Rocco A. Servedio (Columbia University); Erik Waingarten (University of Pennsylvania)

Entropy Regularization and Faster Decremental Matching in General Graphs

Jiale Chen, Aaron Sidford, Ta-Wei Tu (Stanford University)

Unbreakable Decomposition in Close-to-Linear Time

Aditya Anand, Euiwoong Lee (University of Michigan); Jason Li (Carnegie Mellon University); Yaowei Long, Thatchaphol Saranurak (University of Michigan)

Parallel Expander Decomposition: Simple, Fast, and Near-Optimal

Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg (ETH Zurich); Thatchaphol Saranurak (University of Michigan)

Deterministic Online Bipartite Edge Coloring

Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); Ola Svenssson, Radu Vintan (EPFL); David Wajc (Technion --- Israel Institute of Technology)

Relating Interleaving and Frechet Distances via Ordered Merge Trees

Thijs Beurskens (TU Eindhoven); Tim Ophelders (Utrecht University); Bettina Speckmann, Kevin Verbeek (TU Eindhoven)

Quantum Locally Recoverable Codes

Louis Golowich, Venkatesan Guruswami (UC Berkeley)
Even Faster (Delta + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains    
Sayan Bhattacharya (University of Warwick); Martin Costa (Univsersity of Warwick); Shay Solomon, Tianyi Zhang (Tel Aviv University)

Exact Thresholds for Noisy Non-Adaptive Group Testing

Junren Chen (The University of Hong Kong); Jonathan Scarlett (National University of Singapore)

Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation

Ilias Diakonikolas (UW Madison); Daniel M. Kane (University of California, San Diego); Jasper C.H. Lee (University of California, Davis); Thanasis Pittas (UW Madison)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs

Shi Li (Nanjing University)

New Prophet Inequalities via Poissonization and Sharding

Elfarouk Harb (University of Illinois at Urbana-Champaign)

Majorized Bayesian Persuasion and Fair Selection

Siddhartha Banerjee (Cornell); Kamesh Munagala, Yiheng Shen (Duke University); Kangning Wang (Stanford University / Rutgers University)

Unweighted Layered Graph Traversal: Passing a Crown via Entropy Maximization

Xingjian Bai, Christian Coester (University of Oxford); Romain Cosson (Inria, Paris)

Tolls for Dynamic Equilibrium Flows

Julian Schwarz, Lukas Graf, Tobias Harks (University of Passau)

Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets

Shimon Kogan, Merav Parter (Weizmann)

Recognizing Sumsets is NP-Complete

Amir Abboud (Weizmann Institute of Science and INSAIT, University of Sofia "St. Kliment Ohridski"); Nick Fischer (INSAIT, University of Sofia "St. Kliment Ohridski"); Ron Safier, Nathan Wallheimer (Weizmann Institute of Science)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More

Barna Saha (University of California San Diego); Virginia Vassilevska Williams, Yinzhan Xu (Massachusetts Institute of Technology); Christopher Ye (University of California San Diego)

A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix

Yanlin Chen (CWI); Andras Gilyen (Renyi Institute Budapest); Ronald de Wolf (CWI and University of Amsterdam)

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Andreas Bjorklund (ITU Copenhagen, Denmark); Radu Curticapean (University of Regensburg, Germany and ITU Copenhagen, Denmark); Thore Husfeldt (Basic Algorithms Research Copenhagen, ITU Copenhagen, Denmark); Petteri Kaski (Aalto University, Finland); Kevin Pratt (New York University, USA)

Eulerian Graph Sparsification by Effective Resistance Decomposition

Arun Jambulapati (University of Michigan); Sushant Sachdeva (University of Toronto); Aaron Sidford (Stanford University); Kevin Tian (University of Texas at Austin); Yibin Zhao (University of Toronto)

Facet-Hamiltonicity

Hugo Akitaya (University of Massachusetts Lowell); Jean Cardinal (Universite Libre de Bruxelles); Stefan Felsner (TU Berlin); Linda Kleist (TU Braunschweig); Robert Lauff (TU Berlin)

An analogue of Reed's conjecture for digraphs

Ken-ichi Kawarabayashi (National Institute of Informatics); Lucas Picasarri-Arrieta (Universite Cote d'Azur)

Weak coloring numbers of minor-closed graph classes

Jedrzej Hodor (Jagiellonian University); Hoang La (Universite Paris-Saclay); Piotr Micek (Jagiellonian University); Clement Rambaud (Universite Cote d'Azur)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs

Rashmika Goswami (Rutgers University); Aditi Dudeja (University of Salzburg); Michael Saks (Rutgers University)

Tight Sampling Bounds for Eigenvalue Approximation

William William (Swartworth); David P. Woodruff (Carnegie Mellon University)

Differentiable Approximations for Distance Queries

Ahmed Abdelkader (Google); David Mount (University of Maryland)

Clock Auctions Augmented with Unreliable Advice

Vasilis Gkatzelis (Drexel University); Daniel Schoepflin (Rutgers University); Xizhi Tan (Drexel University)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors

Sepehr Assadi (University of Waterloo); Aaron Bernstein, Zach Langley (Rutgers University); Lap Chi Lau, Robert Wang (University of Waterloo)

Fully Dynamic (Delta + 1) Coloring Against Adaptive Adversaries

Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim (Northeastern University)

Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets

Yeyuan Chen (University of Michigan)

A coarse Erdos-Posa theorem

Jungho Ahn (Korea Institute for Advanced Study (KIAS)); J. Pascal Gollin (Institute for Basic Science (IBS)); Tony Huynh (Sapienza University of Rome); O-joung Kwon (Hanyang University and Institute for Basic Science (IBS))

The Submodular Santa Claus Problem

Etienne Bamas (ETH Zurich); Sarah Morell (Technische Universitat Berlin); Lars Rohwedder (Maastricht University)

Breaking the Two Approximation Barrier for Various Consensus Clustering Problems

Debarati Das (Pennsylvania State University); Amit Kumar (Indian Institute of Technology, Delhi)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More

Mina Dalirrooyfard (Morgan Stanley); Andrea Lincoln (Boston University); Barna Saha (University of California, San Diego); Virginia Vassilevska Williams (Massachusetts Institute of Technology)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow

Ohad Trabelsi (Toyota Technological Institute at Chicago)

Strict Self-Assembly of Discrete Self-Similar Fractals in the abstract Tile-Assembly Model

Florent Becker (Universite d'Orleans); Daniel Hader, Matthew J. Patitz (University of Arkansas)

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Joel Rajakumar, James Watson (University of Maryland); Yi-Kai Liu (NIST / University of Maryland)

New Approximation Algorithms and Reductions for n-Pairs Shortest Paths and All-Nodes Shortest Cycles

Shiri Chechik, Itay Hoch, Gur Lifshitz (Tel-Aviv University)

Improved Online Reachability Preservers

Greg Bodwin, Tuong Le (University of Michigan)

Prophet Inequalities: Competing with the Top ell Items is Easy

Mathieu Molina (Inria, FairPlay team); Vianney Perchet (ENSAE & criteo AI Lab); Patrick Loiseau (Inria, FairPlay team); Nicolas Gast (Inria & Univ. Grenoble Alpes)

An Elementary Predictor Obtaining 2 sqrt(T) + 1 Distance to Calibration

Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, Mirah Shi (University of Pennsylvania)

Beating Bellman’s Algorithm for Subset Sum

Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Nick Fischer (INSAIT, University of Sofia "St. Kliment Ohridski”); Vasileios Nakos (National and Kapodistrian University of Athens and Archimedes/ Athena RC)

Platforms for Efficient and Incentive-Aware Collaboration

Nika Haghtalab (UC Berkeley); Mingda Qiao, Kunhe Yang (University of California, Berkeley)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs

Chandra Chekuri (University of Illinois, Urbana-Champaign, USA); Rhea Jain (University of Illinois at Urbana Champaign)

Gains-from-Trade in Bilateral Trade with a Broker

Suho Shin, Gary Peng (University of Maryland); Ilya Hajiaghayi (Takoma Park Middle School); Mohammad Taghi Hajiaghayi (University of Maryland)

Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds

Lingxiao Huang (Nanjing University); Jian Li (Tsinghua University); Pinyan Lu (Shanghai University of Finance and Economics); Xuan Wu (Huawei TCS Lab)

Faster two-dimensional pattern matching with k mismatches

Jonas Ellert (ENS Paris, France); Paweł Gawrychowski, Adam Gorkiewicz (University of Wroclaw, Poland); Tatiana Starikovskaya (ENS Paris, France)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation

Antoine El-Hayek, Monika Henzinger (IST Austria); Jason Li (Carnegie Mellon University)

Locally Testable Tree Codes

Tamer Mour, Alon Rosen (Bocconi University); Ron Rothblum (Technion)

Improved Spectral Density Estimation via Explicit and Implicit Deflation

Rajarshi Bhattacharjee (University of Massachusetts Amherst); Rajesh Jayaram (Google Research); Cameron Musco (University of Massachusetts Amherst); Christopher Musco (New York University); Archan Ray (JP Morgan Chase)

Sublinear-Round Broadcast without Trusted Setup

Andreea B. Alexandru (Duality Technologies); Julian Loss (CISPA Helmholtz Center for Information Security); Charalampos Papamanthou (Yale University); Giorgos Tsimos (University of Maryland); Benedikt Wagner (Ethereum Foundation)

Fully-Distributed Byzantine Agreement in Sparse Networks

John Augustine (IIT Madras); Fabien Dufoulon (Lancaster University); Gopal Pandurangan (University of Houston)

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors

Elena Gribelyuk, Pachara Sawettamalya (Princeton University); Hongxun Wu (UC Berkeley); Huacheng Yu (Princeton University)

Frechet Distance in Subquadratic Time

Siu-Wing Cheng, Haoqiang Huang (Hong Kong University of Science and Technology)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications

Joseph (Seffi) Naor (Technion); Aravind Srinivasan (UMD, College Park); David Wajc (Technion)

New Combinatorial Insights for Monotone Apportionment

Javier Cembrano (TU Berlin); Jose Correa (Universidad de Chile); Ulrike Schmidt-Kraepelin (TU Eindhoven); Alexandros Tsigonias-Dimitriadis (European Central Bank); Victor Verdugo (Pontificia Universidad Catolica de Chile)

On the Decidability of Presburger Arithmetic Expanded with Powers

Toghrul Karimov (Max Planck Institute for Software Systems); Florian Luca (Stellenbosch University); Joris Nieuwveld, Joel Ouaknine (Max Planck Institute for Software Systems); James Worrell (University of Oxford)

A Tight VC-Dimension Analysis of Clustering Coresets with Applications

Vincent Cohen-Addad (Google Research, France); Andrew Draganov (Aarhus University); Matteo Russo (Sapienza, University of Rome); David Saulpic (Universite Paris Cite, CNRS); Chris Schwiegelshohn (Aarhus University)

Quasi-Monte Carlo Beyond Hardy-Krause

Nikhil Bansal (University of Michigan); Haotian Jiang (University of Chicago)

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval

William Kuszmaul (CMU); Aaron Putterman (Harvard University); Tingqiang Xu, Hangrui Zhou (Tsinghua University); Renfei Zhou (CMU)

The Primal Pathwidth SETH

Michael Lampis (Universite Paris-Dauphine)

Faster single-source shortest paths with negative real weights via proper hop distance

Kent Quanrud, Yufan Huang, Peter Jin (Purdue University)

A Cut-Matching Game for Constant-Hop Expanders

Bernhard Haeupler (INSAIT Bulgaria & ETH Zurich); Jonas Huebotter (ETH Zurich); Mohsen Ghaffari (MIT)

Planar graphs in blowups of fans

Vida Dujmovic (University of Ottawa, Canada); Gwenael Joret (Universite Libre de Bruxelles); Piotr Micek (Jagiellonian University); Pat Morin (Carleton University); David R. Wood (Monash University)

All-Hops Shortest Paths

Virginia Vassilevska Williams (Massachusetts Institute of Technology); Zoe Xi, Yinzhan Xu (MIT); Uri Zwick (Tel Aviv University)

A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs

Thomas Hayes (University at Buffalo); Varsha Dani (Rochester Institute of Technology)

FPTAS for Holant Problems with Log-Concave Signatures

Kun He (Renmin University of China); Zhidan Li, Guoliang Qiu, Chihao Zhang (Shanghai Jiao Tong University)

Stronger adversaries grow cheaper forests: online node-weighted Steiner problems

Sander Borst (CWI Amsterdam); Marek Elias, Moritz Venzin (Bocconi University)

The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints

Sven Jager (RPTU Kaiserslautern-Landau, Germany); Alexander Lindermayr, Nicole Megow (University of Bremen, Germany)

A discrete analog of Tutte’s barycentric embeddings on surfaces

Eric Colin de Verdiere (LIGM, CNRS, Universite Gustave Eiffel, F-77454 Marne-la-Vallee, France); Vincent Despre (Universite de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France); Loic Dubois (LIGM, Universite Gustave Eiffel, CNRS, F-77454 Marne-la-Vallee, France)

Flipping Non-Crossing Spanning Trees

Havard Bakke Bjerkevik (University at Albany - SUNY); Linda Kleist (TU Braunschweig); Torsten Ueckerdt (Karlsruhe Institute of Technology); Birgit Vogtenhuber (Graz University of Technology)

On the Locality of Hall's Theorem

Sebastian Brandt (CISPA Helmholtz Center for Information Security); Yannic Maus (TU Graz); Ananth Narayanan (CISPA Helmholtz Center for Information Security); Florian Schager (TU Graz); Jara Uitto (Aalto University)

Solving Polynomial Equations Over Finite Fields

Holger Dell (Goethe University Frankfurt and IT University of Copenhagen); Anselm Haak (Paderborn University); Melvin Kallmayer (Goethe University Frankfurt); Leo Wennmann (Maastricht University)

PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods

SAYAN BANDYAPADHYAY (Portland State University); Katie Clinch (UNSW Sydney); William Lochet (CNRS, LIRMM); Daniel Lokshtanov (University of California Santa Barbara, USA); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai)

Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric

Pankaj K Agarwal (Duke University); Sharath Raghvendra (North Carolina State University); Pouyan Shirzadian (Virginia Tech); Keegan Yao (Duke University)

Integer programs with nearly totally unimodular matrices: the cographic case

Manuel Aprile (Universita di Padova); Samuel Fiorini, Gwenael Joret, Stefan Kober, Michal T. Seweryn (Universite Libre de Bruxelles); Stefan Weltge (Technische Universitat Munchen); Yelena Yuditsky (Universite Libre de Bruxelles)

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Pierre Civit (EPFL); Muhammad Ayaz Dzulfikar, Seth Gilbert (NUS); Rachid Guerraoui, Jovan Komatovic, Manuel Vidigueira (EPFL); Igor Zablotchi (Mysten Labs)

Improved Explicit Near-Optimal Codes in the High-Noise Regimes

Xin Li, Songtao Mao (Johns Hopkins University)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths

Lily Wang, Greg Bodwin (University of Michigan)

Quasilinear-time eccentricities computation, and more, on median graphs

Pierre Berge (Universite Clermont Auvergne, France); Guillaume Ducoffe (University of Bucharest, Romania); Michel Habib (IRIF, Universite Paris Cite, France)

Hermitian Diagonalization in Linear Precision

Rikhav Shah (UC Berkeley)

Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching

Sujoy Bhore (IIT Bombay); Timothy M. Chan (UIUC)

Prophet Secretary and Matching: the Significance of the Largest Item

Ziyun Chen (Tsinghua University); Zhiyi Huang, Dongchen Li (The University of Hong Kong); Zhihao Gavin Tang (Shanghai University of Finance and Economics)

Congestion-Approximators from the Bottom Up

Jason Li, Satish Rao (UC Berkeley); Di Wang (Google)

A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM

Peyman Afshani (Aarhus University); Nodari Sitchinava (University of Hawaii at Manoa)

Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint

Prommy Sultana Hossain (George Mason University); Xintong Wang (Rutgers University); Fang-Yi Yu (George Mason University)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

Sepehr Assadi (University of Waterloo); Soheil Behnezad (Northeastern University); Christian Konrad, Kheeran Naidu (University of Bristol); Janani Sundaresan (University of Waterloo)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

Vikrant Ashvinkumar, Aaron Bernstein (Rutgers University); Adam Karczmarz (University of Warsaw and IDEAS NCBR)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

Daniel Neuen (University of Regensburg); Radu Curticapean (University of Regensburg, IT University of Copenhagen)

Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs

Benjamin Moseley, Aidin Niaparast (Carnegie Mellon University); R. Ravi (CMU)

Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities

Vaishali Surianarayanan, Daniel Lokshtanov (UC Santa Barbara); Saket Saurabh (Institute of Mathematical Science (IMSc)); Jie Xue (New York University Shanghai); Abhishek Sahu (National Institute of Science Education and Research)