2024 SIAM ACM-SIAM Symposium on Discrete Algorithms, ALENEX and SOSA

Sunday, January 7

CP1
SODA Session 1A

9:00 AM - 11:05 AM
Room: Edison D

Chair: Sahil Singla
Georgia Institute of Technology, U.S.

9:00-9:20 Prior-Independent Auctions for Heterogeneous Bidders abstract

Guru Guruganesh, Google Research, U.S.; Aranyak Mehta and Di Wang, Google, Inc., U.S.; Kangning Wang, Stanford University, U.S.

9:25-9:45 Impossibilities for Obviously-Strategy-Proof Mechanisms abstract

Shiri Ron, Weizmann Institute of Science, Israel

9:50-10:10 Revenue Maximization for Buyers with Costly Participation abstract

Yannai A. Gonczarowski and Nicole Immorlica, Microsoft Research, U.S.; Yingkai Li, Yale University, U.S.; Brendan Lucier, Microsoft Research, U.S.

10:15-10:35 Breaking the $3/4$ Barrier for Approximate Maximin Share abstract

Hannaneh Akrami, Max Planck Institute for Informatics, Germany and Saarland University, Germany; Jugal Garg, University of Illinois Urbana-Champaign

10:40-11:00 On the Tractability Frontier of Combinatorial Contracts abstract

Ramiro Deo-Campo Vuong, University of Southern California, U.S.; Paul Duetting, Google Research, U.S.; Shaddin Dughmi, University of Southern California, U.S.; Michal Feldman and Yoav Gal Tzur, Tel Aviv University, Israel; Neel B. Patel and Aditya Prasad, University of Southern California, U.S.

Sunday, January 7

CP2
SODA Session 1B

9:00 AM - 11:05 AM
Room: Edison ABC

Chair: John Iacono
Université libre de Bruxelles and Synapsis Group, Belgium

9:00-9:20 Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns abstract

Parinya Chalermsook, Aalto University, Finland; Seth Pettie, University of Michigan, Ann Arbor, U.S.; Sorrachai Yingchareonthawornchai, Simons Institute and University of California, Berkeley, U.S.

9:25-9:45 Vertical Decomposition in 3D and 4D with Applications to Line Nearest-Neighbor Searching in 3D abstract

Esther Ezra, Bar Ilan University, Israel; Pankaj K. Agarwal, Duke University, U.S.; Micha Sharir, Tel Aviv University, Israel

9:50-10:10 Dynamic Dictionary with Subconstant Wasted Bits Per Key abstract

Tianxiao Li and Jingxun Liang, Tsinghua University, P. R. China; Huacheng Yu, Princeton University, U.S.; Renfei Zhou, Tsinghua University, P. R. China

10:15-10:35 Dynamic Dynamic Time Warping abstract

Karl Bringmann, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, Weizmann Institute of Science, Israel; Ivor Hoog, Technical University of Denmark, Denmark; Evangelos Kipouridis, Saarland University, Germany; Tomasz Kociumaka, Max Planck Institute for Informatics, Germany; Eva Rotenberg, Technical University of Denmark, Denmark

10:40-11:00 Dynamically Maintaining the Persistent Homology of Time Series abstract

Sebastiano Cultrera Di Montesano, Herbert Edelsbrunner, and Monika Henzinger, Institute of Science and Technology Austria, Austria; Lara Ost, University of Vienna, Austria

Sunday, January 7

CP3
SODA Session 1C

9:00 AM - 11:05 AM
Room: Edison EFG

Chair: Daniel Lokshtanov
University of California, Santa Barbara, U.S.

9:00-9:20 Fully Dynamic Approximation Schemes on Planar and Apex-Minor-Free Graphs abstract

Marek Sokolowski, University of Warsaw, Poland; Tuukka Korhonen, University of Bergen, Norway; Wojciech Nadara and Michał Pilipczuk, University of Warsaw, Poland

9:25-9:45 Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations abstract

Baris Can Esmer, Saarland University, Germany; Ariel Kulik and Dániel Marx, CISPA Helmholtz Center for Information Security, Germany; Daniel Neuen, Universität Bremen, Germany; Roohani Sharma, Max Planck Institute for Informatics, Germany

9:50-10:10 Shortest Disjoint Paths on a Grid abstract

Mathieu Mari, University of Montpellier, France; Anish Mukherjee, University of Warwick, United Kingdom; Piotr Sankowski and Michał Pilipczuk, University of Warsaw, Poland

10:15-10:35 Tree Containment Above Minimum Degree is FPT abstract

Fedor Fomin and Petr Golovach, University of Bergen, Norway; Danil Sagunov, V.A. Steklov Mathematical Institute, RAS, Russia; Kirill Simonov, Technische Universität Wien, Austria

10:40-11:00 Determinantal Sieving abstract

Eduard Eiben, Royal Holloway, University of London, United Kingdom; Tomohiro Koana, Technische Universität Berlin, Germany; Magnus Wahlström, Royal Holloway, University of London, United Kingdom

Sunday, January 7

CP41
ALENEX Session 1

9:00 AM - 11:05 AM
Room: Wright

Chair: Rezaul Chowdhury
Stony Brook University, U.S.

9:00-9:20 Constrained Planarity in Practice - Engineering the Synchronized Planarity Algorithm abstract

Simon D. Fink and Ignaz Rutter, University of Passau, Germany

9:25-9:45 A Direct $k$-Way Hypergraph Partitioning Algorithm for Optimizing the Steiner Tree Metric abstract

Tobias Heuer, Karlsruhe Institute of Technology, Germany

9:50-10:10 Parallel Unconstrained Local Search for Partitioning Irregular Graphs abstract

Nikolai Maas, Lars Gottesbüren, and Daniel Seemaier, Karlsruhe Institute of Technology, Germany

10:15-10:35 Fast and Simple Unrooted Dynamic Forests abstract

Benjamin A. Berendsohn, Freie Universität Berlin, Germany

10:40-11:00 Practical Parallel Algorithms for Near-Optimal Densest Subgraphs on Massive Graphs abstract

Pattara Sukprasert, Databricks, U.S.; Quanquan C. Liu, Simons Institute and University of California, Berkeley, U.S.; Laxman Dhulipala, University of Maryland, College Park, U.S.; Julian Shun, Massachusetts Institute of Technology, U.S.

Sunday, January 7

CP4
SODA Session 2A

2:00 PM - 4:05 PM
Room: Edison D

Chair: Simina Branzei
Purdue University, U.S.

2:00-2:20 Minimization Is Harder in the Prophet World abstract

Vasilis Livanos and Ruta Mehta, University of Illinois Urbana-Champaign

2:25-2:45 Bandit Algorithms for Prophet Inequality and Pandora's Box abstract

Yifan Wang, Georgia Institute of Technology, U.S.; Khashayar Gatmiry, Massachusetts Institute of Technology, U.S.; Thomas Kesselheim, Universität Bonn, Germany; Sahil Singla, Georgia Institute of Technology, U.S.

2:50-3:10 Rationality-Robust Information Design: Bayesian Persuasion under Quantal Response abstract

Yiding Feng, Chicago Booth School of Business, U.S.; Chien-Ju Ho, Washington University in St. Louis, U.S.; Wei Tang, Columbia University, U.S.

3:15-3:35 Equilibrium Dynamics in Market Games with Exchangeable and Divisible Resources abstract

José Correa, Universidad de Chile, Chile; Tobias Harks and Anja Schedel, University of Passau, Germany; José Verschae, Pontificia Universidad Católica de Chile, Chile

3:40-4:00 Simple Delegated Choice abstract

Samuel Taggart, Oberlin College, U.S.; Ali Ali Khodabakhsh, University of Texas at Austin, U.S.; Emmanouil Pountourakis, Drexel University, U.S.

Sunday, January 7

CP5
SODA Session 2B

2:00 PM - 4:05 PM
Room: Edison ABC

Chair: Richard Peng
University of Waterloo, Canada

2:00-2:20 Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues abstract

Lap Chi Lau, Kam Chuen Tung, and Robert Wang, University of Waterloo, Canada

2:25-2:45 Cliquewidth and Dimension abstract

Gwenaël Joret, Université Libre de Bruxelles, Belgium; Piotr Micek, Jagiellonian University, Krakow, Poland; Michał Pilipczuk, University of Warsaw, Poland; Bartosz Walczak, Jagiellonian University, Krakow, Poland

2:50-3:10 Single-Source Unsplittable Flows in Planar Graphs abstract

Vera Traub, Universität Bonn, Germany; Laura Vargas Koch and Rico Zenklusen, ETH Zurich, Switzerland

3:15-3:35 2-Approximation for Prize-Collecting Steiner Forest abstract

Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Mohammad Mahdavi, University of Maryland, U.S.

3:40-4:00 An $\tilde\Omega\big(\sqrt{\log |T|}\big)$ Lower Bound for Steiner Point Removal abstract

Yu Chen, École Polytechnique Fédérale de Lausanne, Switzerland; Zihan Tan, Rutgers University, U.S.

Moved to CP11. A Polynomial-Time $\text{opt}^\epsilon$-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph

Wegrzycki Karol, Jana Cslovjecsek, Michał Pilipczuk,

Moved to CP18. Exact Shortest Paths with Rational Weights on the Word Ram

Adam Karczmarz, Wojciech Nadara, Marek Sokolowski,

Sunday, January 7

CP6
SODA Session 2C

2:00 PM - 4:05 PM
Room: Edison EFG

Chair: Karthik C.S.
Rutgers University, New Brunswick, U.S.

2:00-2:20 Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable abstract

Jie Xue, New York University-Shanghai, China; Sayan Bandyapadhyay, Portland State University, U.S.; William Lochet, University of Bergen, Norway; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway

2:25-2:45 Meta-Theorems for Parameterized Streaming Algorithms abstract

Ramanujan M. Sridharan, University of Warwick, United Kingdom; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Pranabendu Misra, Chennai Mathematical Institute, India; Fahad Panolan, University of Leeds, United Kingdom; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Meirav Zehavi, Ben Gurion University, Israel

2:50-3:10 Parameterized Algorithms for Block-Structured Integer Programs with Large Entries abstract

Michał Pilipczuk, University of Warsaw, Poland; Jana Cslovjecsek, École Polytechnique Fédérale de Lausanne, Switzerland; Martin Koutecký, Charles University in Prague, Czech Republic; Alexandra Lassota, Technische Universiteit Eindhoven, The Netherlands; Adam Polak, Bocconi University, Italy

3:15-3:35 Factoring Pattern-Free Permutations into Separable Ones abstract

Édouard Bonnet, CNRS and ENS Lyon, France; Romain Bourneuf, Inria-LIP-ENS Lyon, France; Colin Geniet, ENS Paris Saclay, France; Stéphan Thomassé, École Normale Supérieure de Lyon, France

3:40-4:00 Representative Set Statements for Delta-Matroids and the Mader Delta-Matroid abstract

Magnus Wahlström, Royal Holloway, University of London, United Kingdom

Sunday, January 7

CP42
ALENEX Session 2

2:00 PM - 3:40 PM
Room: Wright

Chair: Gerth S. Brodal
Aarhus University, Denmark

2:00-2:20 Fast Many-to-Many Routing for Dynamic Taxi Sharing with Meeting Points abstract

Moritz Laupichler and Peter Sanders, Karlsruhe Institute of Technology, Germany

2:25-2:45 $2$-Fault-Tolerant Strong Connectivity Oracles abstract

Evangelos Kosinas, Loukas Georgiadis, and Daniel Tsokaktsis, University of Ioannina, Greece

2:50-3:10 Fast and Delay-Robust Multimodal Journey Planning abstract

Jonas Sauer and Dominik Bez, Karlsruhe Institute of Technology, Germany

3:15-3:35 Near-Optimal Coverage Path Planning with Turn Costs abstract

Dominik M. Krupke, Technische Universität Braunschweig, Germany

Sunday, January 7

CP7
SODA Session 3A

4:30 PM - 7:00 PM
Room: Edison D

Chair: Arya Mazumdar
University of California, San Diego, U.S.

4:30-4:50 On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation abstract

Raphael A. Meyer, New York University, U.S.; Cameron Musco, University of Massachusetts, Amherst, U.S.; Christopher Musco, New York University, U.S.

4:55-5:15 Detecting Hidden Communities by Power Iterations with Connections to Vanilla Spectral Algorithms abstract

Chandra Sekhar Mukherjee and Jiapeng Zhang, University of Southern California, U.S.

5:20-5:40 Matrix Perturbation: Davis-Kahan in the Infinity Norm abstract

Abhinav Bhardwaj and Van Vu, Yale University, U.S.

5:45-6:05 A Ptas for $\ell_0$-Low Rank Approximation: Solving Dense CSPS over Reals abstract

Euiwoong Lee, University of Michigan, U.S.; Vincent Cohen-Addad, Google Research, U.S.; Chenglin Fan, Sorbonne Universités, France; Suprovat Ghoshal, Northwestern University, U.S.; Arnaud de Mesmay, Université Gustave Eiffel, France; Alantha Newman, CNRS and Grenoble University, France; Tony Wang, University of Wisconsin-Madison, U.S.

6:10-6:30 Strongly Polynomial Frame Scaling to High Precision abstract

Daniel Dadush and Akshay Ramachandran, Centrum Wiskunde & Informatica, Netherlands

6:35-6:55 Positivity Certificates for Linear Recurrences abstract

Bruno Salvy, Inria Paris-Rocquencourt, France; Alaa Ibrahim, ENS Lyon, France

Sunday, January 7

CP8
SODA Session 3B

4:30 PM - 7:00 PM
Room: Edison ABC

Chair: Peilin Zhong
Google Research, U.S.

4:30-4:50 A Unifying Framework for Differentially Private Sums under Continual Observation abstract

Monika Henzinger, Institute of Science and Technology Austria, Austria; Jalaj Upadhyay, Rutgers University, U.S.; Sarvagya Upadhyay, Fujitsu Research of America, U.S.

4:55-5:15 Optimal Bounds on Private Graph Approximation abstract

Zongrui Zou and Jingcheng Liu, Nanjing University, China; Jalaj Upadhyay, Rutgers University, U.S.

5:20-5:40 Shannon Meets Gray: Noise-Robust, Low-Sensitivity Codes with Applications in Differential Privacy abstract

David R. Lolck and Rasmus Pagh, University of Copenhagen, Denmark

5:45-6:05 Adjacency Sketches in Adversarial Environments abstract

Moni Naor and Eugene Pekel, Weizmann Institute of Science, Israel

6:10-6:30 Sorting and Selection in Rounds with Adversarial Comparisons abstract

Christopher D. Trevisan, University of Waterloo, Canada

6:35-6:55 Deterministic Byzantine Agreement with Adaptive $O(n\cdot F)$ Communication abstract

Fatima Elsheimy, Yale University, U.S.; Giorgos Tsimos, University of Maryland, U.S.; Charalampos Papamanthou, Yale University, U.S.

Sunday, January 7

CP9
SODA Session 3C

4:30 PM - 7:00 PM
Room: Edison EFG

Chair: David M. Mount
University of Maryland, U.S.

4:30-4:50 Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes abstract

Édouard Bonnet, CNRS and ENS Lyon, France; Julien Duron, Inria-LIP-ENS Lyon, France; John Sylvester and Viktor Zamaraev, University of Liverpool, United Kingdom; Maksim Zhukovskii, University of Sheffield, United Kingdom

4:55-5:15 On the Extremal Functions of Acyclic Forbidden 0--1 Matrices abstract

Seth Pettie, University of Michigan, Ann Arbor, U.S.; Gabor Tardos, Renyi Institute, Hungary

5:20-5:40 Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs Is Logarithmic abstract

Jesse Campion Loth and Kevin C. Halasz, Simon Fraser University, Canada; Tomáš Masařík, University of Warsaw, Poland; Bojan Mohar, Simon Fraser University, Canada; Robert Šámal, Charles University, Czech Republic

5:45-6:05 Triangulations Admit Dominating Sets of Size $2n/7$. abstract

Aleksander B. Christiansen, Eva Rotenberg, and Daniel P. Rutschmann, Technical University of Denmark, Denmark

6:10-6:30 The Grid-Minor Theorem Revisited abstract

Pat Morin, Carleton University, Canada; Vida Dujmovic, University of Ottawa, Canada; Robert Hickingbotham, Monash University, Australia; Jedrzej Hodor, Jagiellonian University, Poland; Gwenael Joret, Université Libre de Bruxelles, Belgium; Hoang La, Jagiellonian University, Poland; Piotr Micek, Jagiellonian University, Krakow, Poland; Clement Rambaud, Ecole Normale Supérieure, France; David Wood, Monash University, Australia

6:35-6:55 Partial Coloring Complex, Vertex Decomposability and Tverberg's Theorem with Constraints abstract

Sharareh Alipour, Khatam University, Iran; Amir Jafari, Mohammad Hassan Mazidi, and Seyed Abolfazl Najafian, Sharif University of Technology, Iran

Sunday, January 7

CP43
ALENEX Session 3

4:30 PM - 6:10 PM
Room: Wright

Chair: Tobias Heuer
Karlsruhe Institute of Technology, Germany

4:30-4:50 Counting Polyominoes, Revisited abstract

Gill Barequet and Gil Ben-Shachar, Technion Israel Institute of Technology, Israel

4:55-5:15 Simple and Robust Dynamic Two-Dimensional Convex Hull abstract

Emil T. Gæde, Inge Li Gørtz, Ivor Van Der Hoog, Christoffer Krogh, and Eva Rotenberg, Technical University of Denmark, Denmark

5:20-5:40 Covering Rectilinear Polygons with Area-Weighted Rectangles abstract

Kathrin Hanauer, Martin Seybold, and Julian Unterweger, University of Vienna, Austria

5:45-6:05 Interactive Exploration Of The Temporal Alpha-Shape abstract

Felix Weitbrecht, Universität Stuttgart, Germany

Monday, January 8

CP10
SODA Session 4A

9:00 AM - 11:05 AM
Room: Edison D

Chair: Clifford S. Stein
Columbia University, U.S.

9:00-9:20 Approximating Subset Sum Ratio Faster Than Subset Sum abstract

Karl Bringmann, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, Weizmann Institute of Science, Israel

9:25-9:45 A Parameterized Family of Meta-Submodular Functions abstract

Mehrdad Ghadiri, Massachusetts Institute of Technology, U.S.; Richard Santiago, ETH Zurich, Switzerland; Bruce Shepherd, University of British Columbia, Canada

9:50-10:10 Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs abstract

Aditi Laddha, Yale University, U.S.; Adam Brown, Georgia Institute of Technology, U.S.; Madhusudhan Reddy Pittu, Carnegie Mellon University, U.S.; Mohit Singh, Georgia Institute of Technology, U.S.

10:15-10:35 Tight Approximability for MAX 2-SAT and Relatives, Under UGC abstract

Joshua Brakensiek, Stanford University, U.S.; Neng Huang, University of Chicago, U.S.; Uri Zwick, Tel Aviv University, Israel

10:40-11:00 Gap Amplification for Reconfiguration Problems abstract

Naoto Ohsaka, CyberAgent, Inc., Japan

Monday, January 8

CP11
SODA Session 4B

9:00 AM - 11:05 AM
Room: Edison ABC

Chair: Natan Rubin
Ben-Gurion University, Israel

9:00-9:20 AG Codes Have No List-Decoding Friends: Approaching the Generalized Singleton Bound Requires Exponential Alphabets abstract

Omar Alrabiah, Venkatesan Guruswami, and Ray Li, University of California, Berkeley, U.S.

9:25-9:45 Conflict Checkable and Decodable Codes and Their Applications abstract

Benny Applebaum and Eliran Kachlon, Tel Aviv University, Israel

9:50-10:10 Optimal Thresholds for Latin Squares, Steiner Triple Systems, and Edge Colorings abstract

Vishesh Jain, University of Ilinois at Chicago, U.S.; Huy T. Pham, Stanford University, U.S.

10:15-10:35 A Polynomial-Time $\text{opt}^\epsilon$-Approximation Algorithm for Maximum Independent Set of Connected Subgraphs in a Planar Graph abstract

Wegrzycki Karol, Saarland University and Max Planck Institute for Informatics, Germany; Jana Cslovjecsek, École Polytechnique Fédérale de Lausanne, Switzerland; Michał Pilipczuk, University of Warsaw, Poland

10:40-11:00 The Hierarchy of Hereditary Sorting Operators abstract

Vít Jelínek, Charles University in Prague, Czech Republic; Michal Opler, Czech Technical University, Prague, Czech Republic; Jakub Pekárek, Charles University, Czech Republic

Moved to CP5. Cliquewidth and Dimension

Gwenaël Joret, Piotr Micek, Michał Pilipczuk, Bartosz Walczak,

Monday, January 8

CP12
SODA Session 4C

9:00 AM - 11:05 AM
Room: Edison EFG

Chair: Sanjeev Khanna
University of Pennsylvania, U.S.

9:00-9:20 Cactus Representations in Polylogarithmic Max-Flow via Maximal Isolating Mincuts abstract

Zhongtian He, Princeton University, U.S.; Shang-En Huang, Boston College, U.S.; Thatchaphol Saranaurak, University of Michigan, U.S.

9:25-9:45 Cactus Representation of Minimum Cuts abstract

Zhongtian He, Princeton University, U.S.; Shang-En Huang, Boston College, U.S.; Thatchaphol Saranurak, University of Michigan, U.S.

9:50-10:10 Beyond the Quadratic Time Barrier for Network Unreliability abstract

Ruoxu Cen, Duke University, U.S.; William He, Carnegie Mellon University, U.S.; Jason Li, Simons Institute and University of California, Berkeley, U.S.; Debmalya Panigrahi, Duke University, U.S.

10:15-10:35 On $(1+\epsilon)$-Approximate Flow Sparsifiers abstract

Zihan Tan, Rutgers University, U.S.; Yu Chen, École Polytechnique Fédérale de Lausanne, Switzerland

10:40-11:00 Max $s,t$-Flow Oracles and Negative Cycle Detection in Planar Digraphs abstract

Adam Karczmarz, University of Warsaw, Poland

Monday, January 8

CP44
ALENEX Session 4

9:00 AM - 10:40 AM
Room: Wright

Chair: Laxman Dhulipala
University of Maryland, College Park, U.S.

9:00-9:20 Maintaining Discrete Probability Distributions in Practice abstract

Daniel Allendorf, Goethe Universität Frankfurt, Germany

9:25-9:45 ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force abstract

Hans-Peter Lehmann, Peter Sanders, and Stefan Walzer, Karlsruhe Institute of Technology, Germany

9:50-10:10 Computing $e$-Th Roots in Number Fields abstract

Andrea Lesavourey, Inria, France; Olivier Bernard, Zama, France; Pierre-Alain Fouque, IRISA / Inria Rennes, France

10:15-10:35 Experimental Evaluation of Fully Dynamic K-Means via Coresets abstract

David Saulpic, IST, Austria; Monika Henzinger, Institute of Science and Technology Austria, Austria; Leonhard Sidl, University of Vienna, Austria

Monday, January 8

CP37
Best Paper Presentation #1

1:30 PM - 2:00 PM
Room: Edison D

Chair: David Woodruff
Carnegie Mellon University, U.S.

1:30-1:55 Breaking the Metric Voting Distortion Barrier abstract

Moses Charikar, Prasanna Ramakrishnan, and Kangning Wang, Stanford University, U.S.; Hongxun Wu, University of California, Berkeley, U.S.

Monday, January 8

CP13
SODA Session 5A

2:00 PM - 4:05 PM
Room: Edison D

Chair: Erik Waingarten
University of Pennsylvania, U.S.

2:00-2:20 Composition of Nested Embeddings with An Application to Outlier Removal abstract

Shuchi Chawla and Kristin Sheridan, University of Texas at Austin, U.S.

2:25-2:45 On Approximability of Steiner Tree in $\ell_p$-Metrics abstract

Henry Fleischmann, University of Michigan, U.S.; Karthik C.S., Rutgers University, New Brunswick, U.S.; Surya Teja Gavva, Rutgers University, U.S.

2:50-3:10 Improved Approximations for Ultrametric Violation Distance abstract

Moses Charikar and Ruiquan Gao, Stanford University, U.S.

3:15-3:35 A $(3+\epsilon)$-Approximation Algorithm For The Minimum Sum Of Radii Problem With Outliers And Extensions For Generalized Lower Bounds abstract

Moritz Buchem, Katja Ettmayr, Hugo Rosado, and Andreas Wiese, Technische Universität München, Germany

3:40-4:00 On Deterministically Approximating Total Variation Distance abstract

Weiming Feng, ETH Zurich, Switzerland; Liqiang Liu and Tianren Liu, Peking University, China

Monday, January 8

CP14
SODA Session 5B

2:00 PM - 4:05 PM
Room: Edison ABC

Chair: Francois Le Gall
Nagoya University, Japan

2:00-2:20 The Sharp Power Law of Local Search on Expanders abstract

Nicholas Recker and Simina Branzei, Purdue University, U.S.; Davin Choo, National University of Singapore, Singapore

2:25-2:45 Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank abstract

Nathaniel Harms, École Polytechnique Fédérale de Lausanne, Switzerland; Viktor Zamaraev, University of Liverpool, United Kingdom

2:50-3:10 Computations with Polynomial Evaluation Oracle: Ruling Out Superlinear SETH-based Lower Bounds abstract

Tatiana Belova and Alexander Kulikov, St. Petersburg State University, Russia; Ivan Mihajlin, University of California, San Diego, U.S.; Olga Ratseeva, St. Petersburg State University, Russia; Grigory Reznikov, Steklov Institute of Mathematics, Russia; Denil Sharipov, St. Petersburg University, Russia

3:15-3:35 Count on CFI Graphs for $\#$P-Hardness abstract

Radu Curticapean, Universität Regensburg, Germany

3:40-4:00 On the Hardness of Posslp abstract

Gorav Jindal, Max Planck Institute for Software Systems, Germany; Peter Bürgisser, Technische Universität Berlin, Germany

Monday, January 8

CP15
SODA Session 5C

2:00 PM - 4:05 PM
Room: Edison EFG

Chair: Richard Peng
University of Waterloo, Canada

2:00-2:20 Computing the $5$-Edge-Connected Components in Linear Time abstract

Evangelos Kosinas, University of Ioannina, Greece

2:25-2:45 Edge-Coloring Algorithms for Bounded Degree Multigraphs abstract

Abhishek Dhawan, Georgia Institute of Technology, U.S.

2:50-3:10 Exact Community Recovery in the Geometric SBM abstract

Julia Gaudio, Xiaochun Niu, and Ermin Wei, Northwestern University, U.S.

3:15-3:35 A Faster Combinatorial Algorithm for Maximum Bipartite Matching abstract

Julia Chuzhoy, Toyota Technological Institute at Chicago, U.S.; Sanjeev Khanna, University of Pennsylvania, U.S.

3:40-4:00 Higher-Order Cheeger Inequality for Partitioning with Buffers abstract

Liren Shan, Toyota Technological Institute at Chicago, U.S.; Konstantin Makarychev, Northwestern University, U.S.; Yury Makarychev, Toyota Technological Institute at Chicago, U.S.; Aravindan Vijayaraghavan, Northwestern University, U.S.

Monday, January 8

CP45
SOSA Session 1

2:00 PM - 4:05 PM
Room: Wright

Chair: Merav Parter
Weizmann Institute of Science, Israel

2:00-2:20 Simple Linear-Size Additive Emulators abstract

Gary T. Hoppenworth, University of Michigan, U.S.

2:25-2:45 Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem abstract

Phevos Paschalidis and Ashley Y. Zhuang, Harvard University, U.S.

2:50-3:10 Listing 6-Cycles abstract

Ce Jin and Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.; Renfei Zhou, Tsinghua University, P. R. China

3:15-3:35 Simpler Reductions from Exact Triangle abstract

Timothy M. Chan, University of Illinois Urbana-Champaign; Yinzhan Xu, Massachusetts Institute of Technology, U.S.

3:40-4:00 An Alternate Proof of Near-Optimal Light Spanners abstract

Greg Bodwin, University of Michigan, U.S.

Monday, January 8

CP16
SODA Session 6A

4:30 PM - 6:35 PM
Room: Edison D

Chair: MohammadTaghi Hajiaghayi
University of Maryland, U.S.

4:30-4:50 Dependent Rounding with Strong Negative-Correlation, and Scheduling on Unrelated Machines to Minimize Completion Time abstract

David G. Harris, University of Maryland, U.S.

4:55-5:15 Faster Exact and Approximation Algorithms for Packing and Covering Matroids via Push-Relabel abstract

Kent Quanrud, Purdue University, U.S.

5:20-5:40 New SDP Roundings and Certifiable Approximation for Cubic Optimization abstract

Jun-Ting Hsieh and Pravesh Kothari, Carnegie Mellon University, U.S.; Lucas Pesenti and Luca Trevisan, Bocconi University, Italy

5:45-6:05 New Approximation Bounds for Small-Set Vertex Expansion abstract

Suprovat Ghoshal, Northwestern University, U.S.; Anand Louis, Indian Institute of Science, Bangalore, India

6:10-6:30 On the Hardness of Finding Balanced Independent Sets in Random Bipartite Graphs abstract

Will Perkins, Georgia Institute of Technology, U.S.; Yuzhou Wang, Georgia Institute of Technology, U.S.

Monday, January 8

CP17
SODA Session 6B

4:30 PM - 6:35 PM
Room: Edison ABC

Chair: Francois Le Gall
Nagoya University, Japan

4:30-4:50 An Improved Classical Singular Value Transformation for Quantum Machine Learning abstract

Ainesh Bakshi, Massachusetts Institute of Technology, U.S.; Ewin Tang, University of California, Berkeley, U.S.

4:55-5:15 Viderman's Algorithm for Quantum LDPC Codes abstract

Inbal R. Livni Navon, Anirudh Krishna, and Mary Last Nwoottersame, Stanford University, U.S.

5:20-5:40 Efficient Quantum State Synthesis with One Query abstract

Gregory A. Rosenthal, University of Cambridge and University of Warwick, United Kingdom

5:45-6:05 Quantum Worst-Case to Average-Case Reductions for All Linear Problems abstract

Vahid Asadi, University of Waterloo, Canada; Alexander Golovnev, Georgetown University, U.S.; Tom Gur, University of Warwick, United Kingdom; Igor Shinkar, Simon Fraser University, Canada; Sathyawageeswar Subramanian, University of Cambridge, United Kingdom

6:10-6:30 Recovering the Original Simplicity: Succinct and Deterministic Quantum Algorithm for the Welded Tree Problem abstract

Guanzhong Li, Lvzhou Li, and Jingquan Luo, Sun Yat-sen University, China

Monday, January 8

CP18
SODA Session 6C

4:30 PM - 6:35 PM
Room: Edison EFG

Chair: Jason Li
Simons Institute and University of California, Berkeley, U.S.

4:30-4:50 Nearly Optimal Approximate Dual-Failure Replacement Paths abstract

Shiri Chechik and Tianyi Zhang, Tel Aviv University, Israel

4:55-5:15 Exact Shortest Paths with Rational Weights on the Word Ram abstract

Adam Karczmarz, Wojciech Nadara, and Marek Sokolowski, University of Warsaw, Poland

5:20-5:40 Fault-Tolerant Spanners Against Bounded-Degree Edge Failures: Linearly More Faults, Almost for Free abstract

Greg Bodwin, University of Michigan, U.S.; Bernhard Haeupler, ETH Zurich, Switzerland; Merav Parter, Weizmann Institute of Science, Israel

5:45-6:05 Simpler and Higher Lower Bounds for Shortcut Sets abstract

Zixuan Xu, Virginia Vassilevska Williams, and Yinzhan Xu, Massachusetts Institute of Technology, U.S.

6:10-6:30 Distances and Shortest Paths on Graphs of Bounded Highway Dimension: Simple, Fast, Dynamic abstract

Sébastien Collette, Synapsis Group, Belgium; John Iacono, Université libre de Bruxelles and Synapsis Group, Belgium

Monday, January 8

CP46
SOSA Session 2

4:30 PM - 7:00 PM
Room: Wright

Chair: Seth Pettie
University of Michigan, Ann Arbor, U.S.

4:30-4:50 Simple and Faster Algorithms for Knapsack abstract

Qizheng He, University of Illinois Urbana-Champaign; Zhean Xu, Tsinghua University, P. R. China

4:55-5:15 Simpler Constant Factor Approximation Algorithms For Weighted Flow Time -- Now For Any $p$-Norm abstract

Alexander Armbruster, Technische Universität München, Germany; Lars Rohwedder, Maastricht University, The Netherlands; Andreas Wiese, Technische Universität München, Germany

5:20-5:40 Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs abstract

Sven Jäger, RPTU Kaiserslautern-Landau, Germany; Philipp Warode, Humboldt University at Berlin, Germany

5:45-6:05 The Greedy Algorithm for the Shortest Common Superstring Problem Is a $\frac 12$-Approximation in Terms of Compression: a Simple Proof abstract

Pavel Kalugin, Moscow Institute of Physics and Technology, Russia; Maksim Nikolaev, Steklov Institute of Mathematics, Russia

6:10-6:30 The Public University Secretary Problem abstract

Heather Newman and Benjamin Moseley, Carnegie Mellon University, U.S.; Kirk Pruhs, University of Pittsburgh, U.S.

6:35-6:55 Improved Algorithms for Integer Complexity abstract

Qizheng He, University of Illinois Urbana-Champaign

Tuesday, January 9

CP19
SODA Session 7A

9:00 AM - 11:05 AM
Room: Edison D

Chair: Sahil Singla
Georgia Institute of Technology, U.S.

9:00-9:20 Fair Price Discrimination abstract

Siddhartha Banerjee, Cornell University, U.S.; Kamesh Munagala and Yiheng Shen, Duke University, U.S.; Kangning Wang, Stanford University, U.S.

9:25-9:45 School Redistricting: Wiping Unfairness Off the Map abstract

Jamie Tucker-Foltz and Ariel Procaccia, Harvard University, U.S.; Isaac Robinson, University of Oxford, United Kingdom

9:50-10:10 Oracle Efficient Online Multicalibration and Omniprediction abstract

Christopher Jung, Stanford University, U.S.

10:15-10:35 Improved Approximation Algorithms for the Joint Replenishment Problem with Outliers, and with Fairness Constraints abstract

Varun Suriyanarayana, Cornell University, U.S.; Varun Sivashankar and Siddharth Gollapudi, Microsoft Research, U.S.; David B. Shmoys, Cornell University, U.S.

10:40-11:00 Santa Claus Meets Makespan and Matroids: Algorithms and Reductions abstract

Etienne Bamas, ETH Zurich, Switzerland; Alexander Lindermayr and Nicole Megow, Universität Bremen, Germany; Lars Rohwedder, Maastricht University, The Netherlands; Jens Schlöter, Universität Bremen, Germany

Tuesday, January 9

CP20
SODA Session 7B

9:00 AM - 11:05 AM
Room: Edison ABC

Chair: Sepehr Assadi
University of Waterloo, Canada

9:00-9:20 A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams abstract

Mélanie Cambus, Aalto University, Finland; Fabian Kuhn, Universität Freiburg, Germany; Etna Lindy, Shreyas Pai, and Jara Uitto, Aalto University, Finland

9:25-9:45 An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation abstract

Christian Konrad and Kheeran K. Naidu, University of Bristol, United Kingdom

9:50-10:10 Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model abstract

Itai Dinur, Ben Gurion University, Israel

10:15-10:35 Robust Sparsification for Matroid Intersection with Applications abstract

Chien-Chung Huang, Inria and DIENS (ENS-PSL, CNRS, Inria), Paris, France; Francois Sellier, DI ENS, PSL & Mines Paris, PSL, France

10:40-11:00 Robust 1-Bit Compressed Sensing with Iterative Hard Thresholding abstract

Arya Mazumdar and Namiko Matsumoto, University of California, San Diego, U.S.

Tuesday, January 9

CP21
SODA Session 7C

9:00 AM - 11:05 AM
Room: Edison EFG

Chair: Jason Li
Carnegie Mellon University, U.S.

9:00-9:20 Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time abstract

Jan Van Den Brand and Li Chen, Georgia Institute of Technology, U.S.; Rasmus Kyng, ETH Zurich, Switzerland; Yang Liu, Stanford University, U.S.; Richard Peng, University of Waterloo, Canada; Maximilian Probst Gutenberg, ETH Zurich, Switzerland; Sushant Sachdeva, University of Toronto, Canada; Aaron Sidford, Stanford University, U.S.

9:25-9:45 Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time abstract

Xiaorui Sun and Wenyu Jin, University of Ilinois at Chicago, U.S.; Mikkel Thorup, University of Copenhagen, Denmark

9:50-10:10 Fully Dynamic Shortest Path Reporting Against An Adaptive Adversary abstract

Anastasiia Alokhina and Jan Van Den Brand, Georgia Institute of Technology, U.S.

10:15-10:35 Fully Dynamic Matching: (2-v2)-Approximation in Polylog Update Time abstract

Mohammad Roghani, Stanford University, U.S.; Amir Azarmehr and Soheil Behnezhad, Northeastern University, U.S.

10:40-11:00 Adaptive Out-Orientations with Applications abstract

Chandra Chekuri, University of Illinois Urbana-Champaign; Aleksander Christiansen, Technical University of Denmark, Denmark; Jacob Holm, University of Copenhagen, Denmark; Ivor Van Der Hoog, Technical University of Denmark, Denmark; Kent Quanrud, Purdue University, U.S.; Eva Rotenberg, Technical University of Denmark, Denmark; Chris Schwiegelshohn, Aarhus University, Denmark

Tuesday, January 9

CP47
SOSA Session 3

9:00 AM - 11:05 AM
Room: Wright

Chair: Euiwoong Lee
University of Michigan, U.S.

9:00-9:20 If Edge Coloring Is Hard under Seth, Then Seth Is False abstract

Alexander Kulikov, St. Petersburg State University, Russia; Ivan Mihajlin, University of California, San Diego, U.S.

9:25-9:45 A CS Guide to the Quantum Singular Value Transformation abstract

Ewin Tang, University of California, Berkeley, U.S.; Kevin Tian, Microsoft Research, U.S.

9:50-10:10 Quantum Logspace Computations Are Verifiable abstract

Uma Girish and Ran Raz, Princeton University, U.S.; Wei Zhan, University of Chicago, U.S.

10:15-10:35 Ussr Is in P/poly abstract

Nikhil Balaji, IIT Delhi, India; Samir Datta, Chennai Mathematical Institute and UMI ReLaX, Chennai, India

10:40-11:00 Simple and Tight Complexity Lower Bounds for Solving Rabin Games abstract

Antonio Casares, Université de Bordeaux, France; Michał Pilipczuk and Marcin Pilipczuk, University of Warsaw, Poland; Uéverton Souza, Universidade Federal Fluminense, Brazil; K. S. Thejaswini, University of Warwick, United Kingdom and Institute of Science and Technology, Austria

Tuesday, January 9

CP38
Best Paper Presentation #2

1:30 PM - 2:00 PM
Room: Edison D

Chair: David Woodruff
Carnegie Mellon University, U.S.

1:30-1:55 Deterministic Near-Linear Time Minimum Cut in Weighted Graphs abstract

Jason Li, Simons Institute and University of California, Berkeley, U.S.; Monika Henzinger, Institute of Science and Technology Austria, Austria; Satish Rao, University of California, Berkeley, U.S.; Di Wang, Google, Inc., U.S.

Tuesday, January 9

CP22
SODA Session 8A

2:00 PM - 4:05 PM
Room: Edison D

Chair: Cameron Musco
University of Massachusetts, Amherst, U.S.

2:00-2:20 The Cost of Parallelizing Boosting abstract

Hongxun Wu and Xin Lyu, University of California, Berkeley, U.S.; Junzhao Yang, Tsinghua University, P. R. China

2:25-2:45 How Many Neurons Does It Take to Approximate the Maximum? abstract

Itay M. Safran, Purdue University, U.S.; Daniel Reichman, Cornell University, U.S.; Paul Valiant, Purdue University, U.S.

2:50-3:10 Learning Hard-Constrained Models with One Sample abstract

Anthimos Vardis Kandiros, Massachusetts Institute of Technology, U.S.; Alkis Kalavasis, Yale University, U.S.; Andreas Galanis, University of Oxford, United Kingdom

3:15-3:35 Online Robust Mean Estimation abstract

Daniel Kane, University of California, San Diego, U.S.; Ilias Diakonikolas, University of Wisconsin-Madison, U.S.; Hanshen Xiao, Massachusetts Institute of Technology, U.S.; Sihan Liu, University of California, San Diego, U.S.

3:40-4:00 Optimal Rates for Ranking a Permuted Isotonic Matrix in Polynomial Time abstract

Emmanuel Pilliat, Université de Montpellier, France; Alexandra Carpentier, Universität Potsdam, Germany; Nicolas Verzelen, Université de Montpellier, France

Tuesday, January 9

CP23
SODA Session 8B

2:00 PM - 4:05 PM
Room: Edison ABC

Chair: Martin Farach-Colton
Rutgers University, U.S.

2:00-2:20 Faster Sublinear-Time Edit Distance abstract

Karl Bringmann and Alejandro Cassis, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, Weizmann Institute of Science, Israel; Tomasz Kociumaka, Max Planck Institute for Informatics, Germany

2:25-2:45 Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization abstract

Daniel Gibney, University of Texas at Dallas, U.S.; Ce Jin, Massachusetts Institute of Technology, U.S.; Tomasz Kociumaka, Max Planck Institute for Informatics, Germany; Sharma Thankachan, North Carolina State University, U.S.

2:50-3:10 Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem abstract

Nick Fischer, Weizmann Institute of Science, Israel

3:15-3:35 Sparse Regular Expression Matching abstract

Inge Li Gørtz and Philip Bille, Technical University of Denmark, Denmark

3:40-4:00 Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data abstract

Rajat De and Dominik Kempa, Stony Brook University, U.S.

Tuesday, January 9

CP24
SODA Session 8C

2:00 PM - 4:05 PM
Room: Edison EFG

Chair: Sepehr Assadi
University of Waterloo, Canada

2:00-2:20 Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time abstract

Sayan Bhattacharya and Mart\'{i}n Costa, University of Warwick, United Kingdom; Nadav Panski and Shay Solomon, Tel Aviv University, Israel

2:25-2:45 Dynamic Algorithms for $k$-Center on Graphs abstract

Emilio Cruciani, University of Salzburg, Austria; Sebastian Forster, University of Salzburg, Germany; Gramoz Goranci, University of Vienna, Austria; Yasamin Nazari, Vrije Universiteit Amsterdam, The Netherlands; Antonis Skarlatos, University of Salzburg, Austria

2:50-3:10 Fully Dynamic Consistent K-Center Clustering abstract

Christoph Grunau, ETH Zurich, Switzerland; Jakub Lacki, Google Research, U.S.; Bernhard Haeupler and Václav Rozhon, ETH Zurich, Switzerland; Rajesh Jayaram, Google Research, U.S.

3:15-3:35 Dynamic Algorithms for Matroid Submodular Maximization abstract

Kiarash Banihashem, University of Maryland, U.S.; Leyla Biabani, Eindhoven University of Technology, Netherlands; Samira Goudarzi, MohammadTaghi Hajiaghayi, and Peyman Jabbarzade, University of Maryland, U.S.; Morteza Monemizadeh, Charles University, Czech Republic

3:40-4:00 On Dynamic Graph Algorithms with Predictions abstract

Adam Polak, Bocconi University, Italy; Jan Van Den Brand, Georgia Institute of Technology, U.S.; Sebastian Forster, University of Salzburg, Germany; Yasamin Nazari, Vrije Universiteit Amsterdam, The Netherlands

Tuesday, January 9

CP48
SOSA Session 4

2:00 PM - 4:05 PM
Room: Wright

Chair: Mikkel Thorup
University of Copenhagen, Denmark

2:00-2:20 Finding the Saddlepoint Faster Than Sorting abstract

Justin Dallant, Université libre de Bruxelles, Belgium; Frederik Haagensen, University of Copenhagen, Denmark; Riko Jacob, IT University of Copenhagen, Denmark; László Kozma, Freie Universitaet Berlin, Germany; Sebastian Wild, University of Liverpool, United Kingdom

2:25-2:45 An Enumerative Perspective on Connectivity abstract

Shyan Akmal, Massachusetts Institute of Technology, U.S.

2:50-3:10 Sorting Signed Permutations by Reversals in Nearly-Linear Time abstract

Bartlomiej Dudek and Pawel Gawrychowski, University of Wroclaw, Poland; Tatiana Starikovskaya, École Normale Supérieure Paris, France

3:15-3:35 A General Technique for Searching in Implicit Sets via Function Inversion abstract

Justin Dallant, Université libre de Bruxelles, Belgium; Boris Aronov, New York University, U.S.; Jean Cardinal, Université Libre de Bruxelles, Belgium; John Iacono, Université libre de Bruxelles and Synapsis Group, Belgium

3:40-4:00 Simple Analysis of Priority Sampling abstract

Majid Daliri, New York University, U.S.

Tuesday, January 9

CP25
SODA Session 9A

4:30 PM - 7:00 PM
Room: Edison D

Chair: Cameron Musco
University of Massachusetts, Amherst, U.S.

4:30-4:50 Fast Algorithms for Separable Linear Programs abstract

Sally Dong, University of Washington, U.S.; Gramoz Goranci, University of Vienna, Austria; Lawrence Li and Sushant Sachdeva, University of Toronto, Canada; Guanghao Ye, Massachusetts Institute of Technology, U.S.

4:55-5:15 Integer Programming with GCD Constraints abstract

Rémy Défossez, IMDEA Software Institute, Spain and École Normale Supérieure, France; Christoph Haase, Oxford University, United Kingdom; Alessio Mansutti, IMDEA Software Institute, Spain; Guillermo A. Pérez, University of Antwerp, Belgium

5:20-5:40 Convex Minimization with Integer Minima in $\widetilde O(n^4)$ Time abstract

Haotian Jiang, University of Washington, U.S.; Yin Tat Lee, Microsoft Research and University of Washington, U.S.; Zhao Song, Adobe Research, U.S.; Lichen Zhang, Massachusetts Institute of Technology, U.S.

5:45-6:05 A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions abstract

Arun Jambulapati, University of Washington, U.S.; Yair Carmon, Tel Aviv University, Israel; Aaron Sidford and Yujia Jin, Stanford University, U.S.

6:10-6:30 Arborescences, Colorful Forests, and Popularity abstract

Telikepalli Kavitha, Tata Institute of Fundamental Research, India; Kazuhisa Makino, Kyoto University, Japan; Ildikó Schlotter, Centre for Economic and Regional Studies, Budapest, Hungary; Yu Yokoi, Tokyo Institute of Technology, Japan

6:35-6:55 Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation abstract

Maximilian Gläser and Marc Pfetsch, Technische Universität Darmstadt, Germany

Tuesday, January 9

CP26
SODA Session 9B

4:30 PM - 7:00 PM
Room: Edison ABC

Chair: Pooya Hatami
University of Texas at Austin, U.S.

4:30-4:50 Faster Rectangular Matrix Multiplication by Combination Loss Analysis abstract

François Le Gall, Nagoya University, Japan

4:55-5:15 New Bounds for Matrix Multiplication: from Alpha to Omega abstract

Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu, Massachusetts Institute of Technology, U.S.; Renfei Zhou, Tsinghua University, P. R. China

5:20-5:40 Fast Fourier Transform via Automorphism Groups of Rational Function Fields abstract

Songsong Li and Chaoping Xing, Shanghai Jiao Tong University, China; Omar Alrabiah, University of California, Berkeley, U.S.

5:45-6:05 New Nearly Optimal Black Box Polynomial Root-Finders abstract

Victor Pan, City University of New York, U.S.

6:10-6:30 Deterministic Algorithms for Low-Degree Factors of Constant-Depth Circuits abstract

Varun Ramanathan and Mrinal Kumar, Tata Institute of Fundamental Research, Mumbai, India; Ramprasad Saptharishi, Tata Institute of Fundamental Research, India

6:35-6:55 The Identity Problem in Nilpotent Groups of Bounded Class abstract

Ruiwen Dong, Saarland University, Germany

Tuesday, January 9

CP27
SODA Session 9C

4:30 PM - 7:00 PM
Room: Edison EFG

Chair: Erik Waingarten
University of Pennsylvania, U.S.

4:30-4:50 Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree abstract

Peilin Zhong and Rajesh Jayaram, Google Research, U.S.; Vahab Mirrokni, Google, Inc., U.S.; Shyam Narayanan, Massachusetts Institute of Technology, U.S.

4:55-5:15 Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth abstract

Prathamesh Patil, Huan Li, Sanjeev Khanna, and Nathan White, University of Pennsylvania, U.S.; Arpit Agarwal, Columbia University, U.S.; Chen Wang, Rutgers University, U.S.; Peilin Zhong, Google Research, U.S.

5:20-5:40 A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching abstract

Taisuke Izumi, Naoki Kitamura, and Yutaro Yamaguchi, Osaka University, Japan

5:45-6:05 A Distributed Palette Sparsification Theorem abstract

Maxime Flin, Reykjavik University, Iceland; Mohsen Ghaffari, Massachusetts Institute of Technology, U.S.; Magnús M. Halldórsson, Reykjavik University, Iceland; Fabian Kuhn, Universität Freiburg, Germany; Alexandre Nolin, CISPA Helmholtz Center for Information Security, Germany

6:10-6:30 Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds abstract

Hsin-Hao Su, Nairen Cao, and Shang-En Huang, Boston College, U.S.

6:35-6:55 The Minority Dynamics and the Power of Synchronicity abstract

Isabella Ziccardi, Bocconi University, Italy; Luca Becchetti, Università di Roma "La Sapienza", Italy; Andrea Clementi and Francesco Pasquale, University of Rome II, Tor Vergata, Italy; Luca Trevisan, Bocconi University, Italy; Robin Vacus, Université de Paris, IRIF, CNRS, France

Tuesday, January 9

CP49
SOSA Session 5

4:30 PM - 7:00 PM
Room: Wright

Chair: Jeremy Fineman
Georgetown University, U.S.

4:30-4:50 Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-K Nearest Neighbors abstract

Vaggos Chatziafratis, University of California, Santa Cruz, U.S.; Piotr Indyk, Massachusetts Institute of Technology, U.S.

4:55-5:15 Revisiting Random Points: Combinatorial Complexity and Algorithms abstract

Sariel Har-Peled, University of Illinois Urbana-Champaign; Elfarouk Harb, University of Illinois at Chicago, U.S.

5:20-5:40 Fully Dynamic $k$-Center in Low Dimensions via Approximate Furthest Neighbors abstract

Mordecai Golin and Jinxiang Gan, Hong Kong University of Science and Technology, Hong Kong

5:45-6:05 Detecting Points in Integer Cones of Polytopes Is Double-Exponentially Hard abstract

Marek Sokolowski and Lukasz Kowalik, University of Warsaw, Poland; Alexandra Lassota, Max Plank Institute, Germany; Konrad Majewski and Michał Pilipczuk, University of Warsaw, Poland

6:10-6:30 Convex Approximation and the Hilbert Geometry abstract

Ahmed Abdelkader, Google, Inc., U.S.; David M. Mount, University of Maryland, U.S.

6:35-6:55 Insertion-Only Dynamic Connectivity in General Disk Graphs abstract

Haim Kaplan, Tel Aviv University, Israel; Katharina Klost and Kristin Knorr, Freie Universitaet Berlin, Germany; Wolfgang J. Mulzer, Freie Universität Berlin, Germany; Liam Roditty, Bar-Ilan University, Israel

Wednesday, January 10

CP28
SODA Session 10A

9:00 AM - 11:05 AM
Room: Edison D

Chair: Nikhil Bansal
University of Michigan, U.S.

9:00-9:20 Bin Packing under Random-Order: Breaking the Barrier of 3/2 abstract

Anish S. Hebbar, Duke University, U.S.; Arindam Khan and K. V. N. Sreenivas, Indian Institute of Science, Bengaluru, India

9:25-9:45 Poly-Logarithmic Competitiveness for the $k$-Taxi Problem abstract

Debmalya Panigrahi, Duke University, U.S.; Anupam Gupta, Carnegie Mellon University, U.S.; Amit Kumar, Indian Institute of Technology, Delhi, India

9:50-10:10 Controlling Tail Risk in Online Ski-Rental abstract

Thomas Lavastida, University of Texas at Dallas, U.S.; Michael Dinitz, Johns Hopkins University, U.S.; Sungjin Im, University of California, Merced, U.S.; Benjamin Moseley, Carnegie Mellon University, U.S.; Sergei Vassilvitskii, Google Research, U.S.

10:15-10:35 Breaking the $k/\log k$ Barrier in Collective Tree Exploration via Tree-Mining abstract

Romain Cosson, Inria, France

10:40-11:00 Maintaining Matroid Intersections Online abstract

Niv Buchbinder, Tel Aviv University, Israel; Anupam Gupta and Daniel Hathcock, Carnegie Mellon University, U.S.; Anna R. Karlin, University of Washington, U.S.; Sherry Sarkar, Carnegie Mellon University, U.S.

Wednesday, January 10

CP29
SODA Session 10B

9:00 AM - 11:05 AM
Room: Edison ABC

Chair: Pooya Hatami
University of Texas at Austin, U.S.

9:00-9:20 A Tight Bound for Testing Partition Properties abstract

Asaf Shapira, Tel Aviv University, Israel; Henrique Stagni, São Paulo University, Brazil

9:25-9:45 Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas abstract

Xi Chen, Columbia University, U.S.; Anindya De, University of Pennsylvania, U.S.; Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio, Columbia University, U.S.

9:50-10:10 Uniformity Testing over Hypergrids with Subcube Conditioning abstract

Xi Chen, Columbia University, U.S.; Cassandra Marcussen, Harvard University, U.S.

10:15-10:35 Tight Lower Bound on Equivalence Testing in Conditional Sampling Model abstract

Gunjan Kumar and Diptarka Chakraborty, National University of Singapore, Singapore; Sourav Chakraborty, ISI Kolkata, India

10:40-11:00 Adversarial Low Degree Testing abstract

Kai Zhe Zheng and Dor Minzer, Massachusetts Institute of Technology, U.S.

Wednesday, January 10

CP30
SODA Session 10C

9:00 AM - 11:05 AM
Room: Edison EFG

Chair: David Woodruff
Carnegie Mellon University, U.S.

9:00-9:20 Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs abstract

Yi-Jun Chang, National University of Singapore, Singapore; Da Wei Zheng, University of Illinois Urbana-Champaign

9:25-9:45 An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism abstract

Timothy M. Chan, University of Illinois Urbana-Champaign; Pingan Cheng, Aarhus University, Denmark; Da Wei Zheng, University of Illinois Urbana-Champaign

9:50-10:10 Improved Bounds for Point Selections and Halving Hyperplanes in Higher Dimensions abstract

Natan Rubin, Ben-Gurion University, Israel

10:15-10:35 Solving Fr\'echet Distance Problems by Algebraic Geometric Methods abstract

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

10:40-11:00 Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings abstract

Pankaj Agarwal, Duke University, U.S.; Sharath Raghvendra, North Carolina State University, U.S.; Pouyan Shirzadian, Virginia Tech, U.S.; Keegan Yao, Duke University, U.S.

Wednesday, January 10

CP50
SOSA Session 6

9:00 AM - 11:05 AM
Room: Wright

Chair: Robert Tarjan
Princeton University, U.S.

9:00-9:20 Ssd Wear Leveling with Optimal Guarantees abstract

Tomer Lange, Israel Institute of Technology, Israel; Joseph Naor, Technion Israel Institute of Technology, Israel; Gala Yadgar, Israel Institute of Technology, Israel

9:25-9:45 When Stochastic Rewards Reduce to Deterministic Rewards in Online Bipartite Matching abstract

Rajan Udwani, University of California, Berkeley, U.S.

9:50-10:10 Simple and Asymptotically Optimal Online Bipartite Edge Coloring abstract

Radu Vintan, EPFL, Switzerland; Joakim Blikstad, KTH Royal Institute of Technology, Sweden; Ola Svensson, École Polytechnique Fédérale de Lausanne, Switzerland; David Wajc, Google Research, U.S.

10:15-10:35 A Simple (1 - ?)-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching abstract

Sepehr Assadi, University of Waterloo, Canada

10:40-11:00 Growing a Random Maximal Independent Set Produces a 2-Approximate Vertex Cover abstract

Nate Veldt, Texas A&M University, U.S.

Wednesday, January 10

CP39
Best Student Paper Presentation #1

1:30 PM - 2:00 PM
Room: Edison D

Chair: David Woodruff
Carnegie Mellon University, U.S.

1:30-1:55 Edge-Weighted Online Stochastic Matching: Beating $1-\frac1e$ abstract

Shuyi Yan, University of Copenhagen, Denmark

Wednesday, January 10

CP31
SODA Session 11A

2:00 PM - 4:05 PM
Room: Edison D

Chair: Natan Rubin
Ben-Gurion University, Israel

2:00-2:20 Set Covering with Our Eyes Wide Shut abstract

Anupam Gupta, Carnegie Mellon University, U.S.; Gregory Kehne, University of Texas at Austin, U.S.; Roie Levin, Tel Aviv University, Israel

2:25-2:45 Edge-Disjoint Paths in Expanders: Online with Removals abstract

Rajko Nenadov, University of Auckland, New Zealand; Nemanja Draganic, Oxford University, United Kingdom; Christoph Grunau, ETH Zurich, Switzerland

2:50-3:10 Online Duet Between Metric Embeddings and Minimum-Weight Perfect Matchings abstract

Sujoy Bhore, Indian Institute of Technology Bombay, India; Arnold Filtser, Columbia University, U.S.; Csaba D. Toth, California State University, Northridge, U.S.

3:15-3:35 Power of Posted-Price Mechanisms for Prophet Inequalities abstract

Kiarash Banihashem and MohammadTaghi Hajiaghayi, University of Maryland, U.S.; Dariusz Kowalski and Piotr Krysta, Augusta University, U.S.; Jan Olkowski, University of Maryland, U.S.

3:40-4:00 Combinatorial Stationary Prophet Inequalities abstract

Neel B. Patel, University of Southern California, U.S.; David Wajc, Google Research, U.S.

Wednesday, January 10

CP32
SODA Session 11B

2:00 PM - 4:05 PM
Room: Edison ABC

Chair: Greg Bodwin
University of Michigan, U.S.

2:00-2:20 Faster Algorithms for Bounded Knapsack and Bounded Subset Sum via Fine-Grained Proximity Results abstract

Lin Chen, Texas Tech University, U.S.; Jiayi Lian, Yuchen Mao, and Guochuan Zhang, Zhejiang University, China

2:25-2:45 The Time Complexity of Fully Sparse Matrix Multiplication abstract

Amir Abboud, Weizmann Institute of Science, Israel; Karl Bringmann, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, Weizmann Institute of Science, Israel; Marvin Künnemann, Karlsruhe Institute of Technology, Germany

2:50-3:10 The Effect of Sparsity on $k$-Dominating Set and Related First-Order Graph Properties abstract

Mirza Redzic, Karlsruhe Institute of Technology, Germany; Nick Fischer, Weizmann Institute of Science, Israel; Marvin Künnemann, Karlsruhe Institute of Technology, Germany

3:15-3:35 Fast 2-Approximate All Pairs Shortest Paths, Faster Approximate All Pairs Shortest Paths abstract

Michal Dory, University of Haifa, Israel; Sebastian Forster, University of Salzburg, Germany; Yael Kirkpatrick, Massachusetts Institute of Technology, U.S.; Yasamin Nazari, Vrije Universiteit Amsterdam, The Netherlands; Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.; Tijn de Vos, University of Salzburg, Germany; Barna Saha and Christopher Ye, University of California, San Diego, U.S.

3:40-4:00 Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation abstract

Zixuan Xu, Alina Harbuzova, Ce Jin, and Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.

Wednesday, January 10

CP33
SODA Session 11C

2:00 PM - 4:05 PM
Room: Edison EFG

Chair: David M. Mount
University of Maryland, U.S.

2:00-2:20 Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles abstract

Yan Alves Radtke and Stefan Felsner, Technische Universität, Berlin, Germany ; Johannes Obenaus, Freie Universität Berlin, Germany; Sandro Roch and Manfred Scheucher, Technische Universität Berlin, Germany; Birgit Vogtenhuber, Graz University of Technology, Austria

2:25-2:45 Delaunay Bifiltrations of Functions on Point Clouds abstract

Ángel Javier Alonso and Michael Kerber, Technische Universität, Graz, Austria; Tung Lam, State University of New York, Albany, U.S.; Michael Lesnick, University at Albany, U.S.

2:50-3:10 Fast Approximation Algorithms for Piercing Boxes by Points abstract

Pankaj Agarwal, Duke University, U.S.; Sariel Har-Peled, University of Illinois Urbana-Champaign; Rahul Raychaudhury, Duke University, U.S.; Stavros Sintos, University of Ilinois at Chicago, U.S.

3:15-3:35 Untangling Graphs on Surfaces abstract

Loïc Dubois, CNRS / LIGM Université Gustave Eiffel, France; Éric Colin de Verdière, Université Paris-Est, LIGM, CNRS, ENPC, ESIEE Paris, UPEM, Marne-la-Vallée, France; Vincent Despré, CNRS and University of Lorraine, France

3:40-4:00 Near-Optimal Min-Sum Motion Planning for Two Square Robots in a Polygonal Environment abstract

Alex Steiger and Pankaj Agarwal, Duke University, U.S.; Dan Halperin and Micha Sharir, Tel Aviv University, Israel

Wednesday, January 10

CP51
SOSA Session 7

2:00 PM - 4:05 PM
Room: Wright

Chair: Seth Pettie
University of Michigan, Ann Arbor, U.S.

2:00-2:20 Modern Hashing Made Simple abstract

William Kuszmaul, Massachusetts Institute of Technology, U.S.; Michael A. Bender, Stony Brook University, U.S.; Martin Farach-Colton, Rutgers University, U.S.; John Kuszmaul, Yale University, U.S.

2:25-2:45 Minimum-Cost Paths for Electric Cars abstract

Uri Zwick, Dani Dorfman, and Haim Kaplan, Tel Aviv University, Israel; Robert Tarjan, Princeton University, U.S.; Mikkel Thorup, University of Copenhagen, Denmark

2:50-3:10 Conditional Lower Bounds for Sparse Parameterized 2-Csp: A Streamlined Proof abstract

Karthik C.S., Rutgers University, New Brunswick, U.S.; Dániel Marx, CISPA Helmholtz Center for Information Security, Germany; Marcin Pilipczuk, University of Warsaw, Poland; Uéverton Souza, Universidade Federal Fluminense, Brazil

3:15-3:35 Contention Resolution for the $\ell$-Fold Union of a Matroid via the Correlation Gap abstract

Junkai Song, The University of Hong Kong, Hong Kong; Chandra Chekuri, University of Illinois Urbana-Champaign; Weizhong Zhang, Carnegie Mellon University, U.S.

3:40-4:00 Simpler Distribution Testing with Little Memory abstract

Clément Canonne and Joy Qiping Yang, University of Sydney, Australia

Wednesday, January 10

CP40
Best Student Paper Presentation #2

4:30 PM - 5:00 PM
Room: Edison D

Chair: David Woodruff
Carnegie Mellon University, U.S.

4:30-4:55 New Explicit Constant-Degree Lossless Expanders abstract

Louis Golowich, University of California, Berkeley, U.S.

Wednesday, January 10

CP34
SODA Session 12A

5:00 PM - 7:05 PM
Room: Edison D

Chair: Dana Randall
Georgia Institute of Technology, U.S.

5:00-5:20 Optimality of Glauber Dynamics for General-Purpose Ising Model Sampling and Free Energy Approximation abstract

Dmitriy Kunisky, Yale University, U.S.

5:25-5:45 Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems abstract

Zongchen Chen, University at Buffalo, U.S.

5:50-6:10 Fast Sampling of $b$-Matchings and $b$-Edge Covers abstract

Zongchen Chen, University at Buffalo, U.S.; Yuzhou Gu, Institute for Advanced Studies, U.S.

6:15-6:35 Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses abstract

Nima Anari, Stanford University, U.S.; Vishesh Jain, University of Ilinois at Chicago, U.S.; Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong, Stanford University, U.S.

6:40-7:00 Smoothed Complexity of Swap in Local Graph Partitioning abstract

Emmanouil Vlatakis-Gkaragkounis, University of California, Berkeley, U.S.

Wednesday, January 10

CP35
SODA Session 12B

5:00 PM - 7:05 PM
Room: Edison ABC

Chair: Peilin Zhong
Google Research, U.S.

5:00-5:20 Sublinear Time Low-Rank Approximation of Toeplitz Matrices abstract

Cameron Musco, University of Massachusetts, Amherst, U.S.; Kshiteej Sheth, École Polytechnique Fédérale de Lausanne, Switzerland

5:25-5:45 A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations abstract

Erik Waingarten, University of Pennsylvania, U.S.; Moses Charikar, Stanford University, U.S.; Michael Kapralov, École Polytechnique Fédérale de Lausanne, Switzerland

5:50-6:10 Code Sparsification and Its Applications abstract

Aaron L. Putterman, Harvard University, U.S.; Sanjeev Khanna, University of Pennsylvania, U.S.; Madhu Sudan, Harvard University, U.S.

6:15-6:35 Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory abstract

Arun Jambulapati and Victor Reis, University of Washington, U.S.; Kevin Tian, Microsoft Research, U.S.

6:40-7:00 Quotient Aparsification for Submodular Functions abstract

Kent Quanrud, Purdue University, U.S.

Wednesday, January 10

CP36
SODA Session 12C

5:00 PM - 7:05 PM
Room: Edison EFG

Chair: Karthik C.S.
Rutgers University, New Brunswick, U.S.

5:00-5:20 Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition abstract

Tuukka Korhonen, University of Bergen, Norway; Daniel Lokshtanov, University of California, Santa Barbara, U.S.

5:25-5:45 Odd Cycle Transversal on $P_5$-Free Graphs in Quasi-Polynomial Time abstract

Roohani Sharma, Max Planck Institute for Informatics, Germany; Akanksha Agrawal, Indian Institute of Tecnology Madras, India; Paloma Lima, IT University of Copenhagen, Denmark; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway

5:50-6:10 Sparse Induced Subgraphs in $P_6$-Free Graphs abstract

Maria Chudnovsky and Rose McCarty, Princeton University, U.S.; Marcin Pilipczuk, Michał Pilipczuk, and Pawel Rzazewski, University of Warsaw, Poland

6:15-6:35 Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More abstract

Hsien-Chih Chang and Jonathan Conroy, Dartmouth College, U.S.; Hung Le, University of Massachusetts, Amherst, U.S.; Lazar Milenkovic and Shay Solomon, Tel Aviv University, Israel; Cuong Than, University of Massachusetts, Amherst, U.S.

6:40-7:00 VC Set Systems in Minor-Free (Di)Graphs and Applications abstract

Hung Le, University of Massachusetts, Amherst, U.S.; Christian Wulff-Nilsen, University of Copenhagen, Denmark