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

Sunday, January 12

CP2
SODA Session 1A

9:00 AM - 11:05 AM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Kent Quanrud
Purdue University, U.S.

9:00-9:20 Connectivity Labeling Schemes for Edge and Vertex Faults Via Expander Hierarchies abstract

Yaowei Long, Seth Pettie, and Thatchaphol Saranurak, University of Michigan, U.S.

9:25-9:45 A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs abstract

Daniel Paul-Pena and C. Seshadhri, University of California, Santa Cruz, U.S.

9:50-10:10 Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$ abstract

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

10:15-10:35 Deterministic Edge Connectivity and Max Flow Using Subquadratic Cut Queries abstract

Aditya Anand and Thatchaphol Saranurak, University of Michigan, U.S.; Yunfan Wang, Tsinghua University, China

10:40-11:00 Massively Parallel Minimum Spanning Tree in General Metric Spaces abstract

Amir Azarmehr and Soheil Behnezhad, Northeastern University, U.S.; Rajesh Jayaram and Jakub Lacki, Google Research, U.S.; Vahab Mirrokni, Google, Inc., U.S.; Peilin Zhong, Google Research, U.S.

Sunday, January 12

CP3
SODA Session 1B

9:00 AM - 11:05 AM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Chandra Chekuri
University of Illinois Urbana-Champaign

9:00-9:20 Beyond 2-Approximation for K-Center in Graphs abstract

Yael Kirkpatrick, Ce Jin, and Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.; Nicole Wein, University of Michigan, U.S.

9:25-9:45 Dynamic Consistent $k$-Center Clustering with Optimal Recourse abstract

Sebastian Forster and Antonis Skarlatos, University of Salzburg, Austria

9:50-10:10 Clustering to Minimize Cluster-Aware Norm Objectives abstract

Martin G. Herold, MPI Informatik, Germany; Evangelos Kipouridis, Saarland University and Max Planck Institute for Informatics, Germany; Joachim Spoerhase, University of Liverpool, United Kingdom

10:15-10:35 Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation abstract

Thanasis Pittas and Ilias Diakonikolas, University of Wisconsin-Madison, U.S.; Daniel Kane, University of California, San Diego, U.S.; Jasper Lee, University of California, Davis, U.S.

10:40-11:00 Breaking the Two Approximation Barrier for Various Consensus Clustering Problems abstract

Debarati Das, Pennsylvania State University, U.S.; Amit Kumar, Indian Institute of Technology, Delhi, India

Sunday, January 12

CP4
SODA Session 1C

9:00 AM - 11:05 AM
Room: Grand Ballroom A - 2nd Floor

Chair: Bill Kuszmaul
Carnegie Mellon University, U.S.

9:00-9:20 Relative-Error Monotonicity Testing abstract

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

9:25-9:45 Nearly Tight Bounds on Testing of Metric Properties abstract

Yiqiao Bao, University of Pennsylvania, U.S.; Sampath Kannan, University of Pennsylvania and University of California, Berkeley, U.S.; Erik Waingarten, University of Pennsylvania, U.S.

9:50-10:10 Lower Bounds for Convexity Testing abstract

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

10:15-10:35 Tight Sampling Bounds for Eigenvalue Approximation abstract

William J. Swartworth and David Woodruff, Carnegie Mellon University, U.S.

10:40-11:00 Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching abstract

Tomasz Kociumaka, Max Planck Institute for Informatics, Germany; Jakob Nogler, ETH Zurich, Switzerland; Philip Wellnitz, Max Planck Institute for Informatics, Germany

Sunday, January 12

CP1
ALENEX Session 1

9:00 AM - 10:40 AM
Room: St. Charles - 1st Floor

Chair: Kasmir Gabert
Sandia National Laboratories, U.S.

9:00-9:20 Optimal Neighborhood Exploration for Dynamic Independent Sets abstract

Jannick Borowitz, Ernestine Großmann, and Christian Schulz, Heidelberg University, Germany

9:25-9:45 Engineering Fully Dynamic Exact $\Delta$-Orientation Algorithms abstract

Christian Schulz, Ernestine Großmann, and Henrik Reinstädtler, Heidelberg University, Germany; Fabian Walliser,

9:50-10:10 A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order abstract

Jonas Sauer, University of Bonn, Germany; Arne Beines, Formerly of Argonne National Laboratory, U.S.; Michael Kaibel, Universität Bonn, Germany; Philip Mayer, Universitaet Bonn, Germany; Petra Mutzel, Universität Bonn, Germany

10:15-10:35 Parallel Cluster-BFS and Applications to Shortest Paths abstract

Letong Wang, University of California, Riverside, U.S.; Guy Blelloch, Carnegie Mellon University, U.S.; Yan Gu and Yihan Sun, University of California, Riverside, U.S.

Sunday, January 12

CP6
SODA Session 2A

2:00 PM - 4:05 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Chandra Chekuri
University of Illinois Urbana-Champaign

2:00-2:20 A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints abstract

Jesper Nederlof, Utrecht University, Netherlands; Céline Swennenhuis, University of Utrecht, Netherlands; Karol Wegrzycki, Saarland University and Max Planck Institute for Informatics, Germany

2:25-2:45 Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs abstract

Shi Li, Nanjing University, China

2:50-3:10 Lift-and-Project Integrality Gaps for Santa Claus abstract

Etienne Bamas, ETH Zurich, Switzerland

3:15-3:35 The Submodular Santa Claus Problem abstract

Etienne Bamas, ETH Zurich, Switzerland; Sarah Morell, Technische Universität Berlin, Germany; Lars Rohwedder, Maastricht University, Netherlands

3:40-4:00 A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing abstract

Franziska Eberle, Technische Universität Berlin, Germany; Felix Hommelsheim, Universität Bremen, Germany; Malin Rau, Chalmers University of Technology, Sweden; Stefan Walzer, Karlsruhe Institute of Technology, Germany

Sunday, January 12

CP7
SODA Session 2B

2:00 PM - 4:05 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Soheil Behnezad
Northeastern University, U.S.

2:00-2:20 Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity abstract

Tijn De Vos, University of Salzburg, Austria; Aleksander Christiansen, Technical University of Denmark, Denmark

2:25-2:45 Fully Dynamic Approximate Minimum Cut in Subpolynomial Time Per Operation abstract

Jason M. Li, Carnegie Mellon University, U.S.; Antoine El-Hayek, Institute of Science and Technology, Austria; Monika Henzinger, Institute of Science and Technology Austria, Austria

2:50-3:10 Fully Dynamic Algorithms for Graph Spanners Via Low-Diameter Router Decomposition abstract

Julia Chuzhoy, Toyota Technological Institute at Chicago, U.S.; Merav Parter, Weizmann Institute of Science, Israel

3:15-3:35 Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier abstract

Anton Bukov, Shay Solomon, and Tianyi Zhang, Tel Aviv University, Israel

3:40-4:00 Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams abstract

Janani Sundaresan and Sepehr Assadi, University of Waterloo, Canada; Soheil Behnezhad, Northeastern University, U.S.; Christian Konrad and Kheeran K. Naidu, University of Bristol, United Kingdom

Sunday, January 12

CP8
SODA Session 2C

2:00 PM - 4:05 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Bundit Laekhanukit
Independent Researcher

2:00-2:20 Quartic Quantum Speedups for Planted Inference abstract

Alexander Schmidhuber, Massachusetts Institute of Technology, U.S.; Ryan O'Donnell, Carnegie Mellon University, U.S.; Robin Kothari and Ryan Babbush, Google Research, U.S.

2:25-2:45 Triply Efficient Shadow Tomography abstract

Robbie King, California Institute of Technology, U.S.; David Gosset, University of Waterloo, Canada; Robin Kothari and Ryan Babbush, Google Research, U.S.

2:50-3:10 On Estimating the Trace of Quantum State Powers abstract

Yupan Liu, Nagoya University, Japan; Qisheng Wang, University of Edinburgh, United Kingdom

3:15-3:35 A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix abstract

Yanlin Chen, CWI and QuSoft, Taiwan; Andras Gilyen, Rényi Institute of Mathematics, Budapest; Ronald de Wolf, CWI Amsterdam and University of Amsterdam, Netherlands

3:40-4:00 Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth abstract

Joel Rajakumar, James Watson, and Yi-Kai Liu, University of Maryland, U.S.

Sunday, January 12

CP5
ALENEX Session 2

2:00 PM - 3:40 PM
Room: St. Charles - 1st Floor

Chair: Christian Schulz
Heidelberg University, Germany

2:00-2:20 Graph Neural Networks As Ordering Heuristics for Parallel Graph Coloring abstract

Kenneth Langedal and Fredrik Manne, University of Bergen, Norway

Cancelled 2:25-2:45 Discrete Transforms of Quantized Persistence Diagrams

Vadim Lebovici, Université Sorbonne Paris Nord, France; Matteo Palo, ETH Zurich, Switzerland; Olympio Hacquard, Kyoto University, Japan; Michael E. Van Huffel, ETH Zurich, Switzerland

2:50-3:10 Scalable Multilevel and Memetic Signed Graph Clustering abstract

Felix Hausberger, Marcelo Fonseca Faraj, and Christian Schulz, Heidelberg University, Germany

3:15-3:35 Batched K-Mer Lookup on the Spectral Burrows-Wheeler Transform abstract

Simon J. Puglisi, Jarno Alanko, and Elena Biagi, University of Helsinki, Finland; Joel Mackenzie, University of Queensland, Australia

Sunday, January 12

CP10
SODA Session 3A

4:30 PM - 7:00 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Kent Quanrud
Purdue University, U.S.

4:30-4:50 Lipschitz Continuous Algorithms for Covering Problems abstract

Soh Kumabe, CyberAgent, Inc., Japan; Yuichi Yoshida, National Institute of Informatics, Japan

4:55-5:15 Approximately Counting Knapsack Solutions in Subquadratic Time abstract

Weiming Feng, ETH Zurich, Switzerland; Ce Jin, Massachusetts Institute of Technology, U.S.

5:20-5:40 Balancing Notions of Equity: Trade-Offs Between Fair Portfolio Sizes and Achievable Guarantees abstract

Swati Gupta, Massachusetts Institute of Technology, U.S.; Jai Moondra and Mohit Singh, Georgia Institute of Technology, U.S.

5:45-6:05 Approximating Traveling Salesman Problems Using a Bridge Lemma abstract

Tobias Mömke, Universität Augsburg, Germany; Martin Böhm, University of Wroclaw, Poland; Zachary Friggstad, University of Alberta, Canada; Joachim Spoerhase, University of Liverpool, United Kingdom

6:10-6:30 Min-CSPs on Complete Instances abstract

Aditya Anand and Euiwoong Lee, University of Michigan, U.S.; Amatya Sharma, University of Michigan, Ann Arbor, U.S.

6:35-6:55 Constraint Satisfaction Problems with Advice abstract

Suprovat Ghoshal, Northwestern University, U.S.; Konstantin Makarychev, Northwestern University, U.S.; Yury Makarychev, Toyota Technological Institute at Chicago, U.S.

Sunday, January 12

CP11
SODA Session 3B

4:30 PM - 7:00 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Kangning Wang
Stanford University, U.S.

4:30-4:50 New Prophet Inequalities Via Poissonization and Sharding abstract

Elfarouk Harb, University of Illinois at Chicago, U.S.

4:55-5:15 Prophet Inequalities: Competing with the Top $\ell$ Items Is Easy abstract

Mathieu Molina, Nicolas Gast, and Patrick Loiseau, Inria, France; Vianney Perchet, ENSAE ParisTech, France

5:20-5:40 New Combinatorial Insights for Monotone Apportionment abstract

Javier Cembrano, Max Plank Institute, Germany; Jose Correa, Universidad de Chile, Chile; Ulrike Schmidt-Kraepelin, Eindhoven University of Technology, Netherlands; Alexandros Tsigonias-Dimitriadis, European Central Bank, Frankfurt am Main, Germany; Victor Verdugo, Pontificia Universidad Católica de Chile, Chile

5:45-6:05 Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint abstract

Prommy Sultana Hossain, George Mason University, U.S.; Xintong Wang, Rutgers University, U.S.; Fang-Yi Yu, George Mason University, U.S.

6:10-6:30 An Elementary Predictor Obtaining $2\sqrt{T} + 1$ Distance to Calibration abstract

Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi, University of Pennsylvania, U.S.

6:35-6:55 Prophet Secretary and Matching: the Significance of the Largest Item abstract

Ziyun Chen, University of Washington, U.S.; Zhiyi Huang and Dongchen Li, University of Hong Kong, Hong Kong; Zhihao Tang, Shanghai University of Finance and Economics, China

Sunday, January 12

CP12
SODA Session 3C

4:30 PM - 7:00 PM
Room: Grand Ballroom A - 2nd Floor

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

4:30-4:50 Fixed-Parameter Tractability of Hedge Cut abstract

Fedor Fomin and Petr Golovach, University of Bergen, Norway; Tuukka Korhonen, 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

4:55-5:15 Crossing Number in Slightly Superexponential Time abstract

Jie Xue, New York University-Shanghai, China; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Fahad Panolan, University of Leeds, United Kingdom; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Roohani Sharma, University of Bergen, Norway; Meirav Zehavi, Ben-Gurion University, Israel

5:20-5:40 Packing Short Cycles abstract

Matthias Bentert, Fedor Fomin, and Petr Golovach, University of Bergen, Norway; Tuukka Korhonen, University of Copenhagen, Denmark; William Lochet, CNRS, France; Fahad Panolan, University of Leeds, United Kingdom; M. S. Ramanujan, University of Warwick, United Kingdom; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Kirill Simonov, Technische Universität Wien, Austria

5:45-6:05 Unbreakable Decomposition in Close-to-Linear Time abstract

Aditya Anand and Euiwoong Lee, University of Michigan, U.S.; Jason M. Li, Carnegie Mellon University, U.S.; Yaowei Long and Thatchaphol Saranurak, University of Michigan, U.S.

6:10-6:30 The Primal Pathwidth Seth abstract

Michael Lampis, Université Paris Dauphine, France

6:35-6:55 Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities abstract

Vaishali Surianarayanan and Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Abhishek Sahu, Homi Bhabha National Institute, India; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Jie Xue, New York University-Shanghai, China

Sunday, January 12

CP9
ALENEX Session 3

4:30 PM - 6:10 PM
Room: St. Charles - 1st Floor

Chair: Martin Seybold
University of Vienna, Austria

4:30-4:50 Linear Assignment on Tile-Centric Accelerators: Redesigning Hungarian Algorithm on IPUs abstract

Cheng Huang, Aarhus University, Denmark; Alexander Mathiasen, Independent Researcher; Josef Dean, Graphcore, U.S.; Johannes Langguth, Simula Research Laboratory, Norway; Davide Mottin and Ira Assent, Aarhus University, Denmark

4:55-5:15 Engineering Optimal Parallel Task Scheduling abstract

Matthew Akram, Nikolai Maas, Peter Sanders, Dominik Schreiber, and Wendy Yi, Karlsruhe Institute of Technology, Germany; Jonas Sauer, University of Bonn, Germany

5:20-5:40 Exploring the Landscape of Distributed Graph Sketching abstract

David Tench, Lawrence Berkeley National Laboratory, U.S.; Evan West, Stony Brook University, U.S.; Kenny Zhang, University of Michigan, U.S.; Michael A. Bender and Daniel Delayo, Stony Brook University, U.S.; Martin Farach-Colton, Rutgers University, U.S.; Gilvir Gill, Stony Brook University, U.S.; Tyler Seip, MongoDB; Victor Zhang, Meta Platforms, Inc., U.S.

5:45-6:05 The Constrained Layer Tree Problem and Applications to Solar Farm Cabling abstract

Thomas Bläsius, Max Göttlicher, Sascha Gritzbach, and Wendy Yi, Karlsruhe Institute of Technology, Germany

Moved to CP13. A Greedy Algorithm for Low-Crossing Partitions for General Set Systems

Monika Csikos, Alexandre Louvet, Nabil Mustafa,

Moved to CP13. HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees

Aniss A. Medbouhi, Alejandro García-Castellanos, Giovanni Luca Marchetti, Danica Kragic, Erik Johannes Bekkers,

Moved to CP13. Spiderdan: Matching Augmentation in Demand-Aware Networks

Aleksander Figiel, Darya Melnyk, André Nichterlein, Arash Pourdamghani, Stefan Schmid,

Monday, January 13

CP13
ALENEX Session 4

9:00 AM - 11:05 AM
Room: St. Charles - 1st Floor

Chair: Christian Schulz
Heidelberg University, Germany

9:00-9:20 Constructions, Bounds, and Algorithms for Peaceable Queens abstract

Katie Clinch, University of New South Wales, Australia; Matthew Drescher, University of California, Davis, U.S.; Tony Huynh, Université Libre de Bruxelles, Belgium; Abdallah Saffidine, University of New South Wales, Australia

9:25-9:45 Another L Makes It Better? Lagrange Meets LLL and May Improve BKZ Pre-Processing abstract

Sebastien Balny, Claire Delaplace, and Gilles Dequen, Université de Picardie Jules Verne, France

9:50-10:10 HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees abstract

Aniss A. Medbouhi, KTH Royal Institute of Technology, Sweden; Alejandro García-Castellanos, VU University Amsterdam, Netherlands; Giovanni Luca Marchetti and Danica Kragic, KTH Royal Institute of Technology, Sweden; Erik Johannes Bekkers, University of Amsterdam, Netherlands

10:15-10:35 A Greedy Algorithm for Low-Crossing Partitions for General Set Systems abstract

Monika Csikos and Alexandre Louvet, ; Nabil Mustafa, Université Sorbonne Paris Nord, France

10:40-11:00 Spiderdan: Matching Augmentation in Demand-Aware Networks abstract

Aleksander Figiel, Darya Melnyk, André Nichterlein, Arash Pourdamghani, and Stefan Schmid, Technische Universität Berlin, Germany

Moved to CP9. Linear Assignment on Tile-Centric Accelerators: Redesigning Hungarian Algorithm on IPUs

Cheng Huang, Alexander Mathiasen, Josef Dean, Johannes Langguth, Davide Mottin, Ira Assent,

Moved to CP9. Engineering Optimal Parallel Task Scheduling

Matthew Akram, Nikolai Maas, Peter Sanders, Dominik Schreiber, Wendy Yi, Jonas Sauer,

Monday, January 13

CP14
SODA Session 4A

9:00 AM - 11:05 AM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Emily Fox
University of Texas at Dallas, U.S.

9:00-9:20 Deterministic Online Bipartite Edge Coloring abstract

Joakim Blikstad, KTH Royal Institute of Technology, Sweden; Ola Svensson, École Polytechnique Fédérale de Lausanne, Switzerland; Radu Vintan, EPFL, Switzerland; David Wajc, Technion Israel Institute of Technology, Israel

9:25-9:45 Eulerian Graph Sparsification by Effective Resistance Decomposition abstract

Arun Jambulapati, University of Washington, U.S.; Sushant Sachdeva, University of Toronto, Canada; Aaron Sidford, Stanford University, U.S.; Kevin Tian, Microsoft Research, U.S.; Yibin Zhao, University of Toronto, Canada

9:50-10:10 A Cut-Matching Game for Constant-Hop Expanders abstract

Bernhard Haeupler, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Jonas Huebotter, ETH Zurich, Switzerland; Mohsen Ghaffari, Massachusetts Institute of Technology, U.S.

10:15-10:35 Quasilinear-Time Eccentricities Computation, and More, on Median Graphs abstract

Pierre Bergé, Université Clermont Auvergne, France; Ducoffe Guillaume, University of Bucharest, Romania; Habib Michel, Université Paris Cité, France

10:40-11:00 Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal abstract

Daoyuan Chen and Simon Meierhans, ETH Zurich, Switzerland; Maximilian Probst Gutenberg, ; Thatchaphol Saranurak, University of Michigan, U.S.

Monday, January 13

CP15
SODA Session 4B

9:00 AM - 11:05 AM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Kangning Wang
Stanford University, U.S.

9:00-9:20 A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization abstract

Trung Dang and Shuchi Chawla, University of Texas at Austin, U.S.; Dimitrios Christou, The University of Texas at Austin, U.S.; Zhiyi Huang, University of Texas at Austin, U.S.; Gregory Kehne and Rojin Rezvan, The University of Texas at Austin, U.S.

9:25-9:45 Hiring for An Uncertain Task: Joint Design of Information and Contracts abstract

Matteo Castiglioni, Politecnico di Milano, Italy; Junjie Chen, City University of Hong Kong

9:50-10:10 A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design abstract

Matteo Castiglioni, Politecnico di Milano, Italy; Junjie Chen, City University of Hong Kong; Minming Li, City University of Hong Kong, Hong Kong; Haifeng Xu, University of Chicago, U.S.; Song Zuo, Google Research, U.S.

10:15-10:35 Majorized Bayesian Persuasion and Fair Selection abstract

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

10:40-11:00 Multi-Agent Combinatorial Contracts abstract

Paul Duetting, Google Research, U.S.; Tomer Ezra, Harvard University, U.S.; Michal Feldman, Tel Aviv University, Israel; Thomas Kesselheim, Universität Bonn, Germany

Monday, January 13

CP16
SODA Session 4C

9:00 AM - 11:05 AM
Room: Grand Ballroom A - 2nd Floor

Chair: Bundit Laekhanukit
Independent Researcher

9:00-9:20 Linear Equations with Monomial Constraints and Decision Problems in Abelian-by-Cyclic Groups abstract

Ruiwen Dong, Saarland University, Germany

9:25-9:45 An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition abstract

Pascal Koiran, LIP-ENS Lyon, France

9:50-10:10 Improving the Leading Constant of Matrix Multiplication abstract

Hantao Yu, Columbia University, U.S.; Josh Alman, Columbia University, U.S.

10:15-10:35 Faster Linear Systems and Matrix Norm Approximation Via Multi-Level Sketched Preconditioning abstract

Michal Derezinski, University of Michigan, U.S.; Christopher Musco, New York University, U.S.; Jiaming Yang, University of Michigan, U.S.

10:40-11:00 More Asymmetry Yields Faster Matrix Multiplication abstract

Josh Alman, Columbia University, U.S.; Ran Duan, Tsinghua University, P. R. China; Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu, Massachusetts Institute of Technology, U.S.; Renfei Zhou, Carnegie Mellon University, U.S.

Monday, January 13

CP17
SODA Best Paper and Best Student Paper Prize Session

11:30 AM - 12:45 PM
Room: Grand Ballroom C/D - 2nd Floor

The Best Student Paper Award will be shared by the following two papers: Tight Streaming Lower Bounds for Deterministic Approximate Counting, Yichuan Wang

&

Improved List Size for Folded Reed-Solomon Codes, Shashank Srivastava

The Best Paper Award will be shared by the following two papers: Improved List Size for Folded Reed-Solomon Codes, Shashank Srivastava

&

Quasi-Monte Carlo Beyond Hardy-Krause, Nikhil Bansal and Haotian Jiang

Chair: Debmalya Panigrahi
Duke University, U.S.

11:30-11:50 Improved List Size for Folded Reed-Solomon Codes abstract

Shashank Srivastava, Rutgers University, U.S.

11:55-12:15 Quasi-Monte Carlo Beyond Hardy-Krause abstract

Nikhil Bansal, University of Michigan, U.S.; Haotian Jiang, University of Chicago, U.S.

12:20-12:40 Tight Streaming Lower Bounds for Deterministic Approximate Counting abstract

Yichuan Wang, Tsinghua University, China

Monday, January 13

CP18
SODA Session 5A

2:00 PM - 4:05 PM
Room: Grand Ballroom C/D - 2nd Floor

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

2:00-2:20 A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs abstract

Chandra Chekuri and Rhea Jain, University of Illinois Urbana-Champaign

2:25-2:45 Congestion-Approximators from the Bottom Up abstract

Jason M. Li, Carnegie Mellon University, U.S.

2:50-3:10 (Almost) Ruling Out Seth Lower Bounds for All-Pairs Max-Flow abstract

Ohad Trabelsi, Toyota Technological Institute at Chicago, U.S.

3:15-3:35 Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and All Eccentricities in Graphs abstract

Feodor F. Dragan, Kent State University, U.S.; Guillaume Ducoffe, ICI – National Institute for Research and Development informatics, Romania; Michel Habib, Université Paris, France; Laurent Viennot, Inria, France

3:40-4:00 Flip Dynamics for Sampling Colorings: Improving $(11/6-\varepsilon)$ Using A Simple Metric abstract

Charlie A. Carlson, University of California, Santa Barbara, U.S.; Eric Vigoda, University of California, Santa Barbara, U.S.

Monday, January 13

CP19
SODA Session 5B

2:00 PM - 4:05 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: R Ravi
Carnegie Mellon University, U.S.

2:00-2:20 Testing Approximate Stationarity Concepts for Piecewise Affine Functions abstract

Lai Tian, The Chinese University of Hong Kong, Hong Kong; Anthony So, Chinese University of Hong Kong, Hong Kong

2:25-2:45 Forall-Exist Statements in Pseudopolynomial Time abstract

Eleonore Bach, EPFL, France; Friedrich Eisenbrand, École Polytechnique Fédérale de Lausanne, Switzerland; Thomas Rothvoss, University of Washington, U.S.; Robert Weismantel, ETH Zurich, Switzerland

2:50-3:10 Complexity of Polytope Diameters Via Perfect Matchings abstract

Christian Nöbel and Raphael Steiner, ETH Zurich, Switzerland

3:15-3:35 The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms abstract

Naren S. Manoj and Max Ovsiankin, Toyota Technological Institute at Chicago, U.S.

3:40-4:00 Integer Programs with Nearly Totally Unimodular Matrices: the Cographic Case abstract

Manuel Aprile, Universita di Padova, Italy; Samuel Fiorini and Gwenaël Joret, Université Libre de Bruxelles, Belgium; Stefan Kober, Université libre de Bruxelles, Belgium; Michal Seweryn, Charles University, Prague, Czech Republic; Stefan Weltge, Technische Universität München, Germany; Yelena Yuditsky, McGill University, Canada

Monday, January 13

CP20
SODA Session 5C

2:00 PM - 4:05 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Emily Fox
University of Texas at Dallas, U.S.

2:00-2:20 Flipping Non-Crossing Spanning Trees abstract

Birgit Vogtenhuber, Graz University of Technology, Austria; Håvard Bjerkevik, University at Albany, U.S.; Linda Kleist, Universität Potsdam, Germany; Torsten Ueckerdt, Karlsruhe Institute of Technology, Germany

2:25-2:45 Ptases for Euclidean Tsp with Unit Disk and Unit Square Neighborhoods abstract

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

2:50-3:10 Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching abstract

Sujoy Bhore, Indian Institute of Technology Bombay, India; Timothy M. Chan, University of Illinois Urbana-Champaign

3:15-3:35 Strict Self-Assembly of Discrete Self-Similar Fractals in the Abstract Tile Assembly Model abstract

Florent Becker, Universite d'Orleans, France; Daniel Hader and Matthew Patitz, University of Arkansas, U.S.

3:40-4:00 Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances abstract

Yu Chen, National University of Singapore, Singapore; Zihan Tan, Rutgers University, U.S.

Monday, January 13

CP21
SOSA Session 1: Sublinear Algorithms

2:00 PM - 4:05 PM
Room: St. Charles - 1st Floor

Chair: Iona Bercea
KTH Royal Institute of Technology, Sweden

2:00-2:20 Simple Sublinear Algorithms for (Delta + 1) Vertex Coloring Via Asymmetric Palette Sparsification abstract

Sepehr Assadi and Helia Yazdanyar, University of Waterloo, Canada

2:25-2:45 How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing abstract

John M. Kallaugher and Ojas Parekh, Sandia National Laboratories, U.S.; Nadezhda Voronova, Boston University, U.S.

2:50-3:10 Sublinear-Time Algorithm for MST-Weight Revisited abstract

Gryphon Patlin and Jan van den Brand, Georgia Institute of Technology, U.S.

3:15-3:35 Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space abstract

Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Christian J. Lebeda, Inria, France

3:40-4:00 On Optimal Testing of Linearity abstract

Vipul Arora, National University of Singapore, Singapore; Esty Kelman, Boston University, and Massachusetts Institute of Technology, U.S.; Uri Meir, Tel Aviv University, Israel; Ephraim Linder, Boston University, U.S.

Monday, January 13

CP22
SODA Session 6A

4:30 PM - 6:35 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: R Ravi
Carnegie Mellon University, U.S.

4:30-4:50 On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions abstract

Mete Seref Ahunbay and Martin Bichler, Technical University of Munich, Germany

4:55-5:15 Approximating Competitive Equilibrium by Nash Welfare abstract

Jugal Garg, University of Illinois Urbana-Champaign; Yixin Tao, Shanghai University of Finance and Economics, China; László Végh, Bonn University, Germany

5:20-5:40 Tolls for Dynamic Equilibrium Flows abstract

Julian Schwarz, Tobias Harks, and Lukas Graf, University of Passau, Germany

5:45-6:05 Platforms for Efficient and Incentive-Aware Collaboration abstract

Nika Haghtalab, Mingda Qiao, and Kunhe Yang, University of California, Berkeley, U.S.

6:10-6:30 Clock Auctions Augmented with Unreliable Advice abstract

Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan, Drexel University, U.S.

Monday, January 13

CP23
SODA Session 6B

4:30 PM - 6:35 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Karthik CS
Rutgers University, U.S.

4:30-4:50 Near-Optimal Hierarchical Matrix Approximation from Matrix-Vector Products abstract

Feyza Duman Keles and Tyler Chen, New York University, U.S.; Diana Halikias, Cornell University, U.S.; Cameron Musco, University of Massachusetts, Amherst, U.S.; Christopher Musco, New York University, U.S.; David Persson, École Polytechnique Fédérale de Lausanne, Switzerland

4:55-5:15 Improved Spectral Density Estimation Via Explicit and Implicit Deflation abstract

Rajarshi Bhattacharjee, University of Massachusetts, Amherst, U.S.; Rajesh Jayaram, Google Research, U.S.; Cameron Musco, University of Massachusetts, Amherst, U.S.; Christopher Musco, New York University, U.S.; Archan Ray, Memorial Sloan-Kettering Cancer Center, U.S.

5:20-5:40 On the Decidability of Presburger Arithmetic Expanded with Powers abstract

Toghrul Karimov, Max Planck Institute for Software Systems, Germany; Florian Luca, Stellenbosch University, South Africa; Joris Nieuwveld and Joël Ouaknine, Max Planck Institute for Software Systems, Germany; James Worrell, University of Oxford, United Kingdom

5:45-6:05 Solving Polynomial Equations Over Finite Fields abstract

Holger Dell, IT University of Copenhagen, Denmark; Anselm Haak, Universität Paderborn, Germany; Melvin Kallmayer, Goethe Universität Frankfurt, Germany; Leo Wennmann, Maastricht University, The Netherlands

6:10-6:30 Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture abstract

Andreas Björklund, IT University of Copenhagen, Denmark; Kevin Pratt, New York University, U.S.; Petteri Kaski, Aalto University, Finland; Thore Husfeldt, IT University of Copenhagen, Denmark; Radu Curticapean, University of Regensburg, Germany and IT University of Copenhagen, Denmark

Monday, January 13

CP24
SODA Session 6C

4:30 PM - 6:35 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Debmalya Panigrahi
Duke University, U.S.

4:30-4:50 Private Mean Estimation with Person-Level Differential Privacy abstract

Rose Silver, Carnegie Mellon University, U.S.; Sushant Agarwal, Northeastern University, U.S.; Gautam Kamath, University of Waterloo, Canada; Mahbod Majid, Massachusetts Institute of Technology, U.S.; Argyris Mouzakis, University of Waterloo, Canada; Jonathan Ullman, Northeastern University, U.S.

4:55-5:15 Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions abstract

Jane Lange, Massachusetts Institute of Technology, U.S.; Ephraim Linder and Sofya Raskhodnikova, Boston University, U.S.; Arsen Vasilyan, Michigan State University, U.S.

5:20-5:40 Almost Tight Bounds for Differentially Private Densest Subgraph abstract

Michael Dinitz, Johns Hopkins University, U.S.; Satyen Kale, Apple, France; Silvio Lattanzi, Google Zurich, Switzerland; Sergei Vassilvitskii, Google Research, U.S.

5:45-6:05 Improved Differentially Private Continual Observation Using Group Algebra abstract

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

Monday, January 13

CP25
SOSA Session 2: Randomization

4:30 PM - 6:35 PM
Room: St. Charles - 1st Floor

Chair: Cliff Stein
Columbia University, U.S.

4:30-4:50 A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations abstract

William Kuszmaul, Massachusetts Institute of Technology, U.S.

4:55-5:15 Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size abstract

Kodai Tanaka, Tohoku University, Japan; Shun Sasaki and Kazumasa Shinagawa, Ibaraki University, Japan; Takaaki Mizuki, Tohoku University, Japan

5:20-5:40 A Multilinear Johnson-Lindenstrauss Transform abstract

Antonis Matakos, Petteri Kaski, and Heikki Mannila, Aalto University, Finland

5:45-6:05 Better Gaussian Mechanism Using Correlated Noise abstract

Christian J. Lebeda, Inria, France

6:10-6:30 Ellipsoid Fitting Up to Constant Via Empirical Covariance Estimation abstract

June Wu, University of Chicago, U.S.; Madhur Tulsiani, Toyota Technological Institute at Chicago, U.S.

Tuesday, January 14

CP26
SODA Session 7A

9:00 AM - 11:05 AM
Room: Grand Ballroom C/D - 2nd Floor

Chair: William Umboh
University of Melbourne, Australia

9:00-9:20 Improved Bounds for Fully Dynamic Matching Via Ordered Ruzsa-Szemeredi Graphs abstract

Sepehr Assadi, University of Waterloo, Canada; Sanjeev Khanna, University of Pennsylvania, U.S.; Peter Kiss, University of Vienna, Austria

9:25-9:45 Matching Composition and Efficient Weight Reduction in Dynamic Matching abstract

Aaron Bernstein, Rutgers University, U.S.; Jiale Chen, Stanford University, U.S.; Aditi Dudeja, University of Salzburg, Austria; Zachary Langley, Rutgers University, U.S.; Aaron Sidford and Ta-Wei Tu, Stanford University, U.S.

9:50-10:10 Online Dependent Rounding Schemes for Bipartite Matchings, with Applications abstract

Joseph (Seffi) Naor, Technion Israel Institute of Technology, Israel; Aravind Srinivasan, University of Maryland, College Park, U.S.; David Wajc, Technion Israel Institute of Technology, Israel; Tristan Pollner, Stanford University, U.S.

10:15-10:35 Entropy Regularization and Faster Decremental Matching in General Graphs abstract

Jiale Chen, Aaron Sidford, and Ta-Wei Tu, Stanford University, U.S.

10:40-11:00 New Philosopher Inequalities for Online Bayesian Matching, Via Pivotal Sampling abstract

Mark Braverman, Princeton University, U.S.; Mahsa Derakhshan, Northeastern University, U.S.; Tristan Pollner and Amin Saberi, Stanford University, U.S.; David Wajc, Technion Israel Institute of Technology, Israel

Tuesday, January 14

CP27
SODA Session 7B

9:00 AM - 11:05 AM
Room: Toulouse - 2nd Floor Mezzanine

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

9:00-9:20 Bounding $\varepsilon$-Scatter Dimension Via Metric Sparsity abstract

Romain Bourneuf, Inria-LIP-ENS Lyon, France; Marcin Pilipczuk, University of Warsaw, Poland

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

Erik Waingarten, University of Pennsylvania, U.S.; Moses Charikar, Stanford University, U.S.

9:50-10:10 Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models Via Truncated Metrics abstract

Moses Charikar, Spencer Compton, and Chirag Pabbaraju, Stanford University, U.S.

10:15-10:35 Highway Dimension: a Metric View abstract

Andreas E. Feldmann, University of Sheffield, United Kingdom; Arnold Filtser, Bar-Ilan University, Israel

10:40-11:00 Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares abstract

Hongjie Chen, ETH Zurich, Switzerland; Deepak Narayanan Sridharan, ETH Zurich, Switzerland; David Steurer, ETH Zurich, Switzerland

Tuesday, January 14

CP28
SODA Session 7C

9:00 AM - 11:05 AM
Room: Grand Ballroom A - 2nd Floor

Chair: Artur Czumaj
University of Warwick, United Kingdom

9:00-9:20 An Analogue of Reed's Conjecture for Digraphs abstract

Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta, National Institute of Informatics, Japan

9:25-9:45 Weak Coloring Numbers of Minor-Closed Graph Classes abstract

Jedrzej Hodor, Jagiellonian University, Poland; Hoang La, CNRS, Université Paris-Saclay, France; Piotr Micek, Jagiellonian University, Krakow, Poland; Clément Rambaud, CEPAM - CNRS, France

9:50-10:10 Unique-Neighbor Expanders with Better Expansion for Polynomial-Sized Sets abstract

Yeyuan Chen, University of Michigan, Ann Arbor, U.S.

10:15-10:35 A Coarse Erd\H{o}s-P\'{o}sa Theorem abstract

Jungho Ahn, Korea Institute for Advanced Study, Korea; Jochen Pascal Gollin, University of Primorska, Slovenia; Tony Huynh, Université Libre de Bruxelles, Belgium; O-Joung Kwon, Hanyang University, South Korea

10:40-11:00 Planar Graphs in Blowups of Fans abstract

Pat Morin, Carleton University, Canada

Tuesday, January 14

CP29
SOSA Session 3: Data Structures and Preprocessing

9:00 AM - 11:05 AM
Room: St. Charles - 1st Floor

Chair: Robert Tarjan
Princeton University, U.S.

9:00-9:20 Multi-Dimensional Approximate Counting abstract

Dingyu Wang, University of Michigan, U.S.

9:25-9:45 3sum in Preprocessed Universes: Faster and Simpler abstract

Adam Polak, Bocconi University, Italy; Shashwat Kasliwal and Pratyush Sharma, IIT Delhi, India

9:50-10:10 Optimal Prefix-Suffix Queries with Applications abstract

Solon P. Pissis, CWI, Amsterdam, Netherlands

10:15-10:35 Pure Binary Finger Search Trees abstract

Gerth S. Brodal and Casper Rysgaard, Aarhus University, Denmark

10:40-11:00 A Simple Algorithm for Dynamic Carpooling with Recourse abstract

Yuval Efron, Shyamal Patel, and Cliff Stein, Columbia University, U.S.

Tuesday, January 14

CP30
SODA Session 8A

2:00 PM - 4:05 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Mike Dinitz
Johns Hopkins University, U.S.

2:00-2:20 Streaming Algorithms Via Local Algorithms for Maximum Directed Cut abstract

Santhoshini Velusamy, Toyota Technological Institute at Chicago, U.S.; Raghuvansh Saxena, Microsoft Research, U.S.; Noah Singer, Carnegie Mellon University, U.S.; Madhu Sudan, Harvard University, U.S.

2:25-2:45 Universal Perfect Samplers for Incremental Streams abstract

Dingyu Wang, University of Michigan, U.S.; Seth Pettie, University of Michigan, Ann Arbor, U.S.

2:50-3:10 Streaming and Communication Complexity of Load-Balancing Via Matching Contractors abstract

Sepehr Assadi, University of Waterloo, Canada; Aaron Bernstein, Rutgers University, U.S.; Zach Langley, Rutgers University, U.S.; Lap Chi Lau and Robert Wang, University of Waterloo, Canada

3:15-3:35 Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits abstract

Yuchen He, Zichun Ye, and Chihao Zhang, Shanghai Jiao Tong University, China

3:40-4:00 Near-Optimal Relative Error Streaming Quantile Estimation Via Elastic Compactors abstract

Hongxun Wu, University of California, Berkeley, U.S.; Elena Gribelyuk, Pachara Sawettamalya, and Huacheng Yu, Princeton University, U.S.

Tuesday, January 14

CP31
SODA Session 8B

2:00 PM - 4:05 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Hung Le
University of Massachusetts, Amherst, U.S.

2:00-2:20 A Fast Algorithm for Computing Zigzag Representatives abstract

Tamal K. Dey, Purdue University, U.S.; Tao Hou, University of Oregon, U.S.; Dmitriy Morozov, Lawrence Berkeley National Laboratory, U.S.

2:25-2:45 Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes abstract

Mook Kwon Jung, Seokyun Kang, and Hee-Kap Ahn, POSTECH, Korea

2:50-3:10 Partitioning a Polygon Into Small Pieces abstract

Mikkel Abrahamsen, Nichlas Rasmussen, and Mads Jensen, University of Copenhagen, Denmark

3:15-3:35 Computing the Second and Third Systoles of a Combinatorial Surface abstract

Matthijs Ebbens, University of Cologne, Germany; Francis Lazarus, Universite Grenoble, France

3:40-4:00 An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs abstract

Natan Rubin, Ben-Gurion University, Israel

Tuesday, January 14

CP32
SODA Session 8C

2:00 PM - 4:05 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Venkat Guruswami
University of California, Berkeley, U.S.

2:00-2:20 Hardness of Counting Small Induced Subgraphs: Fourier vs. Sylow abstract

Philip Wellnitz and Simon Döring, Max Planck Institute for Informatics, Germany; Dániel Marx, CISPA Helmholtz Center for Information Security, Germany; Radu Curticapean, University of Regensburg, Germany and IT University of Copenhagen, Denmark; Daniel Neuen, Max Planck Institute for Informatics, Germany

2:25-2:45 Maximum Span Hypothesis: A Potentially Weaker Assumption Than Gap-ETH for Parameterized Complexity abstract

Karthik C. S., Rutgers University, U.S.; Subhash Khot, New York University, U.S.

2:50-3:10 Parameterizing the quantification of CMSO: model checking on minor-closed graph classes abstract

Ignasi Sau, CNRS, LIRMM, France; Giannos Stamoulis, University of Warsaw, Poland; Dimitrios Thilikos, CNRS, LIRMM, France

3:15-3:35 Losing Treewidth In The Presence Of Weights abstract

Michal Wlodarczyk, University of Warsaw, Poland

3:40-4:00 Finding irrelevant vertices in linear time on bounded-genus graphs abstract

Petr Golovach, University of Bergen, Norway; Stavros Kolliopoulos, National and Kapodistrian University of Athens, Greece; Giannos Stamoulis, University of Warsaw, Poland; Dimitrios Thilikos, CNRS, LIRMM, France

Tuesday, January 14

CP33
SOSA Session 4: Optimization, Parallel and Distributed Algorithms

2:00 PM - 4:05 PM
Room: St. Charles - 1st Floor

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

2:00-2:20 Bidirectional Dijkstra's Algorithm Is Instance-Optimal abstract

Bernhard Haeupler, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Richard Hladík, Sofia University, Bulgaria; Václav Rozhon, ETH Zurich, Switzerland; Robert Tarjan, Princeton University, U.S.; Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria

2:25-2:45 A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path abstract

Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Bernhard Haeupler, ETH Zurich, Switzerland; Rustam Latypov, Aalto University, Finland; Antti Roeyskoe and Aurelio L. Sulser, ETH Zurich, Switzerland

2:50-3:10 Efficient Matroid Intersection Via a Batch-Update Auction Algorithm abstract

Joakim Blikstad, KTH Royal Institute of Technology, Sweden; Ta-Wei Tu, Stanford University, U.S.

3:15-3:35 Trading Prophets: How to Trade Multiple Stocks Optimally abstract

Surbhi Rajput, Ashish Chiplunkar, and Rohit Vaish, Indian Institute of Technology, Delhi, India

3:40-4:00 A Simple Lower Bound for Set Agreement in Dynamic Networks abstract

Pierre Fraigniaud, Universite Paris Sud & CNRS, France; Minh Hang Nguyen, Université Paris Cité, France; Ami Paz, CNRS LISN, Universite Paris-Saclay, France

Tuesday, January 14

CP35
SODA Session 9A

4:30 PM - 7:00 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: William Umboh
University of Melbourne, Australia

4:30-4:50 Competitive Strategies to Use "Warm Start" Algorithms with Predictions abstract

Avrim Blum, Toyota Technological Institute at Chicago, U.S.; Vaidehi Srinivas, Northwestern University, U.S.

4:55-5:15 Online Scheduling Via Gradient Descent for Weighted Flow Time Minimization abstract

Qingyun Chen, Sungjin Im, and Aditya Petety, University of California, Merced, U.S.

5:20-5:40 Stronger Adversaries Grow Cheaper Forests: Online Node-Weighted Steiner Problems abstract

Sander Borst, Centrum Wiskunde & Informatica, Netherlands; Marek Elias and Moritz Venzin, Bocconi University, Italy

5:45-6:05 Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs abstract

Benjamin Moseley, Aidin Niaparast, and R. Ravi, Carnegie Mellon University, U.S.

6:10-6:30 Unweighted Layered Graph Traversal: Passing a Crown Via Entropy Maximization abstract

Romain Cosson, Inria, France; Xingjian Bai, Massachusetts Institute of Technology, U.S.; Christian Coester, University of Oxford, United Kingdom

6:35-6:55 The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints abstract

Sven Jäger, RPTU Kaiserslautern-Landau, Germany; Alexander Lindermayr and Nicole Megow, Universität Bremen, Germany

Tuesday, January 14

CP36
SODA Session 9B

4:30 PM - 7:00 PM
Room: Toulouse - 2nd Floor Mezzanine

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

4:30-4:50 Efficient $d$-Ary Cuckoo Hashing at High Load Factors by Bubbling Up abstract

William Kuszmaul, Carnegie Mellon University, U.S.; Michael Mitzenmacher, Harvard University, U.S.

4:55-5:15 Fast and Simple Sorting Using Partial Information abstract

Richard Hladík, Sofia University, Bulgaria; Bernhard Haeupler, ETH Zurich, Switzerland; John Iacono, Université libre de Bruxelles, Belgium; Václav Rozhon, ETH Zurich, Switzerland; Robert Tarjan, Princeton University, U.S.; Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria

5:20-5:40 Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval abstract

Aaron L. Putterman, Harvard University, U.S.; William Kuszmaul, Carnegie Mellon University, U.S.; Tingqiang Xu and Hangrui Zhou, Tsinghua University, P. R. China; Renfei Zhou, Carnegie Mellon University, U.S.

5:45-6:05 A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM abstract

Peyman Afshani, Aarhus University, Denmark; Nodari Sitchinava, University of Hawaii at Manoa, U.S.

6:10-6:30 Top-K Document Retrieval in Compressed Space abstract

Gonzalo Navarro, University of Chile, Chile; Yakov Nekrich, Michigan Technological University, U.S.

6:35-6:55 Faster Two-Dimensional Pattern Matching with $k$ Mismatches abstract

Jonas Ellert, ENS Paris Saclay, France; Pawel Gawrychowski and Adam Gorkiewicz, University of Wroclaw, Poland; Tatiana Starikovskaya, École Normale Supérieure Paris, France

Tuesday, January 14

CP37
SODA Session 9C

4:30 PM - 7:00 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Rajmohan Rajaraman
Northeastern University, U.S.

4:30-4:50 Parks and Recreation: Color Fault-Tolerant Spanners Made Local abstract

Asaf Petruschka, Merav Parter, Shay Sapir, and Elad Tzalik, Weizmann Institute of Science, Israel

4:55-5:15 Asynchronous 3-Majority Dynamics with Many Opinions abstract

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

5:20-5:40 Sublinear-Round Broadcast Without Trusted Setup abstract

Andreea Alexandru, Duality Technologies, U.S.; Julian Loss, CISPA Helmholtz Center for Information Security, Germany; Charalampos Papamanthou, Yale University, U.S.; Giorgos Tsimos, University of Maryland, U.S.; Benedikt Wagner, Ethereum Foundation, Switzerland

5:45-6:05 Fully-Distributed Byzantine Agreement in Sparse Networks abstract

John Augustine, IIT Mumbai, India; Fabien Dufoulon, Lancaster University, United Kingdom ; Gopal Pandurangan, University of Houston, U.S.

6:10-6:30 On the Locality of Hall's Theorem abstract

Sebastian Brandt, CISPA Helmholtz Center for Information Security, Germany; Yannic Maus, Technische Universität, Graz, Austria; Ananth Narayanan, CISPA Helmholtz Center for Information Security, Germany; Florian Schager, TU Graz; Jara Uitto, Aalto University, Finland

6:35-6:55 Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement abstract

Pierre Civit, EPFL, Switzerland; Ayaz Dzulfikar and Seth Gilbert, National University of Singapore, Singapore; Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira, EPFL, Switzerland; Igor Zablotchi, Mysten Labs, Greece

Tuesday, January 14

CP34
SOSA Session 5: Approximation Algorithms for Graphs

4:30 PM - 6:35 PM
Room: St. Charles - 1st Floor

Chair: Tobias Mömke
Universität Augsburg, Germany

4:30-4:50 Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique abstract

Yijia Chen, Shanghai Jiao Tong University, China; Yi Feng, Shanghai University of Finance and Economics, China; Bundit Laekhanukit, Independent Researcher; Yanlin Liu, Ocean University of China, Qiandao, China

4:55-5:15 Validating a Ptas for Triangle-Free 2-Matching abstract

Yusuke Kobayashi and Takashi Noguchi, Kyoto University, Japan

5:20-5:40 Simple Approximation Algorithms for Polyamorous Scheduling abstract

Yuriy Biktairov, University of Southern California, U.S.; Leszek Gasieniec, University of Liverpool, United Kingdom; Wanchote Po Jiamjitrak, University of Helsinki, Finland; N Namrata and Benjamin Smith, University of Liverpool, United Kingdom; Sebastian Wild, University of Marburg, Germany

5:45-6:05 Spectral Sparsification by Deterministic Discrepancy Walk abstract

Lap Chi Lau and Robert Wang, University of Waterloo, Canada; Hong Zhou, Fuzhou University, China

6:10-6:30 Simple Length-Constrained Minimum Spanning Trees abstract

Ellis Hershkowitz and Richard Huang, Brown University, U.S.

Wednesday, January 15

CP38
SODA Session 10A

9:00 AM - 11:05 AM
Room: Grand Ballroom C/D - 2nd Floor

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

9:00-9:20 Spanners in Planar Domains Via Steiner Spanners and Non-Steiner Tree Covers abstract

Hung Le, University of Massachusetts, Amherst, U.S.; Sujoy Bhore, IIT Bombay, India; Balázs Keszegh, Renyi Institute, Hungary ; Andrey Kupavskii, CNRS - Ecole Normale Superieure, France; Alexandre Louvet, ; Dömötör Pálvölgyi, MTA-ELTE, Budapest; Csaba D. Toth, California State University, Northridge, U.S.

9:25-9:45 A Lower Bound for Light Spanners in General Graphs abstract

Greg Bodwin and Jeremy Flics, University of Michigan, U.S.

9:50-10:10 Subquadratic Algorithms in Minor-Free Digraphs: (weighted) Distance Oracles, Decremental Reachability, and More abstract

Adam Karczmarz, University of Warsaw, Poland; Da Wei Zheng, University of Illinois Urbana-Champaign

10:15-10:35 Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets abstract

Shimon Kogan and Merav Parter, Weizmann Institute of Science, Israel

10:40-11:00 Improved Online Reachability Preservers abstract

Greg Bodwin and Tuong Le, University of Michigan, U.S.

Wednesday, January 15

CP39
SODA Session 10B

9:00 AM - 11:05 AM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Venkat Guruswami
University of California, Berkeley, U.S.

9:00-9:20 New Separations and Reductions for Directed Hopsets and Preservers abstract

Yinzhan Xu, Massachusetts Institute of Technology, U.S.; Gary Hoppenworth, University of Michigan, U.S.; Zixuan Xu, Massachusetts Institute of Technology, U.S.

9:25-9:45 Tree Independence Number IV. Even-Hole-Free Graphs abstract

Maria Chudnovsky, Princeton University, U.S.; Peter Gartland, University of California, Santa Barbara, U.S.; Sepehr Hajebi, University of Waterloo, Canada; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Sophie Spirkl, University of Waterloo, Canada

9:50-10:10 A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices abstract

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

10:15-10:35 Recognizing Sumsets is NP-Complete abstract

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

10:40-11:00 A Topological Proof Of The Hell–Nešetril Dichotomy abstract

Sebastian Meyer, TU Dresden, Germany; Jakub Opršal, University of Birmingham, United Kingdom

Wednesday, January 15

CP40
SODA Session 10C

9:00 AM - 11:05 AM
Room: Grand Ballroom A - 2nd Floor

Chair: Avrim Blum
Toyota Technological Institute at Chicago, U.S.

9:00-9:20 Sumsets, 3SUM, Subset Sum: Now for Real! abstract

Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria

9:25-9:45 New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching abstract

Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Ce Jin and Yinzhan Xu, Massachusetts Institute of Technology, U.S.

9:50-10:10 Beating Bellman's Algorithm for Subset Sum abstract

Karl Bringmann, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Vasileios Nakos, National & Kapodistrian University of Athens, Greece

10:15-10:35 Average-Case Hardness of Parity Problems: Orthogonal Vectors, K-Sum and More abstract

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

10:40-11:00 Exact Thresholds for Noisy Non-Adaptive Group Testing abstract

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

Wednesday, January 15

CP41
SOSA Session 6: Graphs

9:00 AM - 11:05 AM
Room: St. Charles - 1st Floor

Chair: Sepehr Assadi
University of Waterloo, Canada

9:00-9:20 Simpler Optimal Sorting from a Directed Acyclic Graph abstract

Ivor Van Der Hoog, Eva Rotenberg, and Daniel P. Rutschmann, Technical University of Denmark, Denmark

9:25-9:45 Finding Longer Cycles Via Shortest Colourful Cycle abstract

Andreas Björklund and Thore Husfeldt, IT University of Copenhagen, Denmark

9:50-10:10 Connectivity Certificate Against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults abstract

Elad Tzalik and Merav Parter, Weizmann Institute of Science, Israel

10:15-10:35 A Simplified Parameterized Algorithm for Directed Feedback Vertex Set abstract

Ziliang Xiong and Mingyu Xiao, University of Electronic Science and Technology of China, China

10:40-11:00 Connectivity Carcass of a Vertex Subset in a Graph - Both Odd and Even Case abstract

Surender Baswana and Abhyuday Pandey, Indian Institute of Technology, Kanpur, India

Wednesday, January 15

CP42
SODA Session 11A

2:00 PM - 4:05 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Rajmohan Rajaraman
Northeastern University, U.S.

2:00-2:20 Inapproximability of Maximum Diameter Clustering for Few Clusters abstract

Ashwin Padaki, University of Pennsylvania, U.S.; Henry Fleischmann, Carnegie Mellon University, U.S.; Kyrylo Karlov, Charles University, Czech Republic; Karthik C. S., Rutgers University, U.S.; Stepan ZHARKOV, Columbia University, U.S.

2:25-2:45 Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds abstract

Lingxiao Huang, Nanjing University, China; Jian Li, Tsinghua University, P. R. China; Pinyan Lu, Shanghai University of Finance and Economics, China; Xuan Wu, Nanyang Technological University, Singapore

2:50-3:10 A Tight Vc-Dimension Analysis of Clustering Coresets with Applications abstract

Chris Schwiegelshohn, Aarhus University, Denmark; Vincent Cohen-Addad, Google Research, U.S.; Andrew Draganov, Aarhus University, Denmark; Matteo Russo, Università La Sapienza, Rome, Italy; David Saulpic, IST, Austria

3:15-3:35 Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric abstract

Pankaj K. 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.

3:40-4:00 Gains-from-Trade in Bilateral Trade with a Broker abstract

Suho Shin, University of Maryland, U.S.; Ilya Hajiaghayi, Takoma Park Middle School; MohammadTaghi Hajiaghayi and Gary Peng, University of Maryland, U.S.

Wednesday, January 15

CP43
SODA Session 11B

2:00 PM - 4:05 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Soheil Behnezad
Northeastern University, U.S.

2:00-2:20 Faster Vizing and Near-Vizing Edge Coloring Algorithms abstract

Sepehr Assadi, University of Waterloo, Canada

2:25-2:45 A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs abstract

Thomas P. Hayes, University at Buffalo, U.S.; Varsha Dani, Rochester Institute of Technology, U.S.

2:50-3:10 Even Faster (Delta + 1)-Edge Coloring Via Shorter Multi-Step Vizing Chains abstract

Martin Costa and Sayan Bhattacharya, University of Warwick, United Kingdom; Shay Solomon, Tel Aviv University, Israel; Tianyi Zhang, ETH Zurich, Switzerland

3:15-3:35 Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs abstract

Aditi Dudeja, University of Salzburg, Austria; Rashmika Goswami and Michael Saks, Rutgers University, U.S.

3:40-4:00 Fully Dynamic $(\Delta+1)$ Coloring Against Adaptive Adversaries abstract

Omer Wasim, Soheil Behnezhad, and Rajmohan Rajaraman, Northeastern University, U.S.

Wednesday, January 15

CP44
SODA Session 11C

2:00 PM - 4:05 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Hung Le
University of Massachusetts, Amherst, U.S.

2:00-2:20 Relating Interleaving and Fréchet Distances Via Ordered Merge Trees abstract

Thijs Beurskens, TU Eindhoven, The Netherlands; Tim Ophelders, TU Eindhoven and Utrecht University, The Netherlands; Bettina Speckmann and Kevin Verbeek, Technische Universiteit Eindhoven, The Netherlands

2:25-2:45 Facet-Hamiltonicity abstract

Hugo A. Akitaya, University of Massachusetts, Lowell, U.S.; Jean Cardinal, Université Libre de Bruxelles, Belgium; Stefan Felsner, Technische Universität, Berlin, Germany ; Linda Kleist, Universität Potsdam, Germany; Robert Lauff, Technische Universität Berlin, Germany

2:50-3:10 Differentiable Approximations for Distance Queries abstract

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

3:15-3:35 Fr\'echet Distance in Subquadratic Time abstract

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

3:40-4:00 A Discrete Analog of Tutte’s Barycentric Embeddings 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é, Université Henri Poincaré, Loria, France

Wednesday, January 15

CP45
SOSA Session 7: Algebraic Techniques

2:00 PM - 4:05 PM
Room: St. Charles - 1st Floor

Chair: Thore Husfeldt
IT University of Copenhagen, Denmark

2:00-2:20 The Quasi-Probability Method and Applications for Trace Reconstruction abstract

Ittai Rubinstein, Massachusetts Institute of Technology, U.S.

2:25-2:45 A Parametric Version of the Hilbert Nullstellensatz abstract

Klara Nosan, Université Paris Cité, France; Rida Ait El Manssour, Oxford University, United Kingdom; Nikhil Balaji, Indian Institute of Technology, Delhi, India; Mahsa Shirmohammadi, Université Paris Cité, France; James Worrell, University of Oxford, United Kingdom

2:50-3:10 Experimental Design Using Interlacing Polynomials abstract

Lap Chi Lau and Robert Wang, University of Waterloo, Canada; Hong Zhou, Fuzhou University, China

3:15-3:35 Revisiting Tree Canonization using polynomials abstract

V. Arvind, Chennai Mathematical Institute, India; Samir Datta, Chennai Mathematical Institute and UMI ReLaX, Chennai, India; SALMAN Faris, BITS Pilani, India; Asif Khan, Chennai Mathematical Institute and UMI ReLaX, Chennai, India

3:40-4:00 Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems abstract

Josh Alman, Alexandr Andoni, and Hengjie Zhang, Columbia University, U.S.

Wednesday, January 15

CP47
SODA Session 12A

4:30 PM - 7:00 PM
Room: Grand Ballroom C/D - 2nd Floor

Chair: Mike Dinitz
Johns Hopkins University, U.S.

4:30-4:50 Fine-Grained Optimality of Partially Dynamic Shortest Paths and More abstract

Christopher Ye, University of California, San Diego, U.S.; Barna Saha, University of California, San Diego, U.S.; Virginia Vassilevska Williams and Yinzhan Xu, Massachusetts Institute of Technology, U.S.

4:55-5:15 All-Hops Shortest Paths abstract

Yinzhan Xu, Virginia Vassilevska Williams, and Zoe Xi, Massachusetts Institute of Technology, U.S.; Uri Zwick, Tel Aviv University, Israel

5:20-5:40 New Approximation Algorithms and Reductions for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles abstract

Shiri Chechik, Itay Hoch, and Gur Lifshitz, Tel Aviv University, Israel

5:45-6:05 Faster Single-Source Shortest Paths with Negative Real Weights Via Proper Hop Distance abstract

Yufan Huang, Peter Jin, and Kent Quanrud, Purdue University, U.S.

6:10-6:30 Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-Offs Between Fault-Tolerance and Subpaths abstract

Greg Bodwin and Lily Wang, University of Michigan, U.S.

6:35-6:55 Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs abstract

Vikrant Ashvinkumar, Rutgers University, U.S.; Aaron Bernstein, Rutgers University, U.S.; Adam Karczmarz, University of Warsaw, Poland

Wednesday, January 15

CP48
SODA Session 12B

4:30 PM - 7:00 PM
Room: Toulouse - 2nd Floor Mezzanine

Chair: Bill Kuszmaul
Carnegie Mellon University, U.S.

4:30-4:50 R\'enyi-Infinity Constrained Sampling with $D^3$ Membership Queries abstract

Yunbum Kook, Georgia Institute of Technology, U.S.; Matthew Zhang, University of Toronto, Canada

4:55-5:15 Potential Hessian Ascent: The Sherrington-Kirkpatrick Model abstract

Juspreet Singh Sandhu, University of California, Santa Cruz, U.S.; David Jekel, University of Copenhagen, Denmark; Jonathan Shi, University of California, San Diego, U.S.

5:20-5:40 Spectral Independence Beyond Total Influence on Trees and Related Graphs abstract

Xiaoyu Chen, Nanjing University, China; Xiongxin Yang, Northeast Normal University, People's Republic of China; Yitong Yin and Xinyuan Zhang, Nanjing University, China

5:45-6:05 Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree abstract

Charlie A. Carlson, University of California, Santa Barbara, U.S.; Xiaoyu Chen, Nanjing University, China; Weiming Feng, ETH Zurich, Switzerland; Eric Vigoda, University of California, Santa Barbara, U.S.

6:10-6:30 Mean-Field Potts and Random-Cluster Dynamics from High-Entropy Initializations abstract

Antonio Blanca, Pennsylvania State University, U.S.; Reza Gheissari, Northwestern University, U.S.; Xusheng Zhang, Pennsylvania State University, U.S.

6:35-6:55 FPTAS for Holant Problems with Log-Concave Signatures abstract

Kun He, Chinese Academy of Sciences, China; Zhidan Li, Guoliang Qiu, and Chihao Zhang, Shanghai Jiao Tong University, China

Wednesday, January 15

CP49
SODA Session 12C

4:30 PM - 7:00 PM
Room: Grand Ballroom A - 2nd Floor

Chair: Yossi Azar
Tel Aviv University, Israel

4:30-4:50 Low Degree Local Correction Over the Boolean Cube abstract

Prashanth Amireddy, Harvard University, U.S.; Amik Raj Behera, Manaswi Paraashar, and Srikanth Srinivasan, University of Copenhagen, Denmark; Madhu Sudan, Harvard University, U.S.

4:55-5:15 Quantum Locally Recoverable Codes abstract

Louis Golowich and Venkatesan Guruswami, University of California, Berkeley, U.S.

5:20-5:40 Locally Testable Tree Codes abstract

Tamer Mour and Alon Rosen, Bocconi University, Italy; Ron Rothblum, Technion Israel Institute of Technology, Israel

5:45-6:05 Improved Explicit Near-Optimal Codes in the High-Noise Regimes abstract

Xin Li and Songtao Mao, Johns Hopkins University, U.S.

6:10-6:30 More Efficient Approximate $k$-Wise Independent Permutations from Random Reversible Circuits Via Log-Sobolev Inequalities abstract

William He, Carnegie Mellon University, U.S.; Lucas Gretta and Angelos Pelecanos, University of California, Berkeley, U.S.

6:35-6:55 Hermitian Diagonalization in Linear Precision abstract

Rikhav Shah, University of California, Berkeley, U.S.

Wednesday, January 15

CP46
SOSA Session 8: Geometry in Low and High Dimensions

4:30 PM - 6:35 PM
Room: St. Charles - 1st Floor

Chair: Hugo A. Akitaya
University of Massachusetts, Lowell, U.S.

4:30-4:50 Dynamic Independent Set of Disks (and Hypercubes) Made Easier abstract

Sujoy Bhore, Indian Institute of Technology Bombay, India; Timothy M. Chan, University of Illinois Urbana-Champaign

4:55-5:15 A Simple Partially Embedded Planarity Test Based on Vertex-Addition abstract

Simon D. Fink, Technische Universität Wien, Austria; Ignaz Rutter, University of Passau, Germany; Sandhya T P, Stockholms Universitet, Sweden

5:20-5:40 An Optimal Algorithm for Half-Plane Hitting Set abstract

Gang Liu and Haitao Wang, University of Utah, U.S.

5:45-6:05 On Beating $2^n$ for the Closest Vector Problem abstract

Rajendra Kumar, Indian Institute of Technology, Delhi, India; Amir Abboud, Weizmann Institute of Science, Israel and INSAIT, Sofia University, Bulgaria

6:10-6:30 Recursive Lattice Reduction-A Framework for Finding Short Lattice Vectors abstract

Divesh Aggarwal, National University of Singapore, Singapore; Thomas Espitau, PQShield; Spencer Peters, Cornell University, U.S.; Noah Stephens-Davidowitz, New York University, U.S.