SODA 2026 — 37th ACM-SIAM Symposium on Discrete Algorithms
January 11–14, 2026 · Vancouver, Canada
Saturday, January 10
5:00 PMRegistration
6:00 PMWelcome Reception
Sunday, January 11
8:00 AMRegistration
8:30 AMContinental Breakfast
9:00 AM - 11:00 AM CP1 SODA 1A: Approximation Algorithms
Regency C - 3rd Floor		 CP2 SODA 1B: Algorithmic Graph Theory
Regency D - 3rd Floor		 CP3 SODA 1C:Combinatorics and Discrete Math
Plaza B - 2nd Floor		 CP4 SODA 1D: Lower bound+complexity theory
Plaza C - 2nd Floor
9:00 Lower Bounds for the Universal TSP on the Plane
Cosmas Kravaris, Princeton University, U.S.		 From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Daniel Dadush, Centrum Wiskunde & Informatica, Netherlands; James Orlin, Massachusetts Institute of Technology, U.S.; Aaron Sidford, Stanford University, U.S.; László A. Végh, University of Bonn, Germany		 Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension
Kunal Dutta and Karol Pisula, University of Warsaw, Poland		 Computational Complexity in Property Testing
Renato Ferreira Pinto JR., Columbia University, U.S.; Diptaksho Palit and Sofya Raskhodnikova, Boston University, U.S.
9:20 Tight Differentially Private PCA via Matrix Coherence
Tommaso D'Orsi, Bocconi University, Italy; Gleb Novikov, Lucerne School of Computer Science, Switzerland		 Centered Colorings in Minor-Closed Graph Classes
Jedrzej Hodor, Jagiellonian University, Poland; Hoang La, CNRS, Université Paris-Saclay, France; Piotr Micek, Jagiellonian University, Krakow, Poland; Clément Rambaud, Université de Nice Cote d'Azur, France		 An Unconditional Lower Bound for the Active-Set Method in Convex Quadratic Maximization
Eleon Bach, Technische Universität München, Germany; Yann Disser, Technische Universität Darmstadt, Germany; Sophie Huiberts, CNRS, France; Nils Mosis, Technische Universität Darmstadt, Germany		 Feature Selection and Junta Testing Are Statistically Equivalent
Nathan Harms, University of British Columbia, Canada; Lorenzo Beretta, IBM Corporation, U.S.; Caleb Koch, Stanford University, U.S.
9:40 Improved Approximation for Ranking on General Graphs
Tao Yu and Mahsa Derakhshan, Northeastern University, U.S.; Mohammad Roghani, Stanford University, U.S.; Mohammad Saneian, Northeastern University, U.S.		 On the Computation of Schrijver's Kernels
Vincent Delecroix and Oscar Fontaine, Université de Bordeaux, France; Francis Lazarus, Universite Grenoble, France		 Interaction Between Skew-Representability, Tensor Products, Extension Properties, and Rank Inequalities
Kristóf Bérczi, Eötvös Loránd University, Hungary; Boglárka Gehér, Alfréd Rényi Institute of Mathematics, Hungary; András Imolay, Eötvös Loránd University, Hungary; László Lovász, Alfréd Rényi Institute of Mathematics, Hungary; Carles Padró, Universidad Politecnica de Catalunya, Spain; Tamás Schwarcz, London School of Economics and Political Science, United Kingdom		 Halfspaces Are Hard to Test with Relative Error
Xi Chen, Columbia University, U.S.; Anindya De, University of Pennsylvania, U.S.; Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, and Tianqi Yang, Columbia University, U.S.
10:00 Online Connectivity Augmentation
Aditya Subramanian, Indian Institute of Science, India; Mohit Garg, Eindhoven University of Technology, Netherlands and University of Bremen, Germany		 From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Aaron Bernstein, New York University, U.S.; Jiale Chen, Stanford University, U.S.		 Finite Pinwheel Scheduling: the K-Visits Problem
Sotiris Kanellopoulos and Christos Pergaminelis, National Technical University of Athens, Greece; Maria Kokkou, Université de Provence Aix Marseille 1, France; Euripides Markou, University of Ioannina, Greece; Aris Pagourtzis, National Technical University of Athens, Greece		 You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Technion Israel Institute of Technology, Israel; Ariel Kulik, Ben Gurion University, Israel; Hadas Shachnai, Technion, Israel
10:20 Stochastic Embedding of Digraphs into Dags
Arnold Filtser, Bar Ilan University, Israel		 Determinization of Min-Plus Weighted Automata Is Decidable
Shaull Almagor, Guy Arbel, and Sarai Sheinvald, Technion Israel Institute of Technology, Israel		 Cell-Probe Lower Bounds Via Semi-Random Csp Refutation: Simplified and the Odd-Locality Case
Weiqiang Yuan, École Polytechnique Fédérale de Lausanne, Switzerland; Venkatesan Guruswami and Xin Lyu, University of California, Berkeley, U.S.		 Short Circuit Walks in Fixed Dimension
Alexander E. Black, Bowdoin College, U.S.
10:40 Low-Sensitivity Matching Via Sampling from Gibbs Distributions
Yuichi Yoshida and Zhang Zihan, National Institute of Informatics, Japan		 Minimum $s$-$t$ Cuts with Fewer Cut Queries
Yonggang Jiang, Max Planck Institute, Germany; Danupon Nanongkai, Max Planck Institute for Informatics, Germany; Pachara Sawettamalya, Princeton University, U.S.		 A Classification of Long-Refinement Graphs for Colour Refinement
Sandra Kiefer and T. Devini De Mel, University of Oxford, United Kingdom		 Space-Efficient Population Protocols for Exact Majority on General Graphs
Joel Rybicki, Jakob Solnerzik, Olivier Stietel, and Robin Vacus, Humboldt University at Berlin, Germany
11:00 AMCoffee Break
11:25 AMIP1 Can We Speed Safely?
Ronitt Rubinfeld (Massachusetts Institute of Technology, U.S.)
12:25 PMLunch
1:55 PM - 3:55 PM CP5 SODA 2A: Approximation Algorithms
Regency C - 3rd Floor		 CP6 SODA 2B:Combinatorics and Discrete Math
Regency D - 3rd Floor		 CP7 SODA 2C:Randomized/Probabilistic Method
Plaza B - 2nd Floor		 CP8 SODA 2D:Dynamic Algorithms/Scheduling
Plaza C - 2nd Floor
1:55 Deterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
Antoine El-Hayek, Institute of Science and Technology, Austria; Monika Henzinger, Institute of Science and Technology Austria, Austria; Jason M. Li, Carnegie Mellon University, U.S.		 Language Generation in the Limit: Noise, Loss, and Feedback
Yannan Bai, Debmalya Panigrahi, and Ian Zhang, Duke University, U.S.		 Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
Michal Derezinski, University of Michigan, U.S.; Aaron Sidford, Stanford University, U.S.		 Deterministic Dynamic Edge Colouring
Aleksander Christiansen, Technical University of Denmark, Denmark
2:15 Combinatorial Selection with Costly Information
Dimitrios Christou and Shuchi Chawla, University of Texas at Austin, U.S.; Amit Harlev and Ziv Scully, Cornell University, U.S.		 Unbounded Error Correcting Codes
Or Zamir, Tel Aviv University, Israel; Klim Efremenko, Ben Gurion University, Israel		 Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
Deeparnab Chakrabarty, Dartmouth College, U.S.; Lorenzo Beretta, IBM Corporation, U.S.; C Seshadhri, University of California, Santa Cruz, U.S.		 History-Independent Load Balancing
Rose Silver, Carnegie Mellon University, U.S.; Michael A. Bender, Stony Brook University, U.S.; William Kuszmaul, Carnegie Mellon University, U.S.; Elaine Shi,
2:35 Coloring 3-Colorable Graphs with Low Threshold Rank
Jun-Ting Hsieh, Massachusetts Institute of Technology, U.S.		 Generating Pivot Gray Codes for Spanning Trees of Complete Graphs in Constant Amortized Time
Dennis Wong, Bowie Liu, Chan-Tong Lam, and Sio-Kei Im, Macao Polytechnic University, Macao		 On Sampling Two Spin Models Using the Local Connective Constant
Charilaos Efthymiou, University of Warwick, United Kingdom		 Dynamic Hierarchical J-Tree Decomposition and Its Applications
Zöcklein Gernot, Institute of Science and Technology Austria, Austria; Gramoz Goranci, University of Vienna, Austria; Monika Henzinger, Institute of Science and Technology Austria, Austria; Peter Kiss and Ali Momeni, University of Vienna, Austria
2:55 Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment
Benjamin Holmgren, Alex Steiger, and Pankaj Agarwal, Duke University, U.S.		 Excluding a Line Minor Via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure
Daniel Dadush, Centrum Wiskunde & Informatica, Netherlands; Friedrich Eisenbrand, École Polytechnique Fédérale de Lausanne, Switzerland; Rom Pinchasi, Technion Israel Institute of Technology, Israel; Thomas Rothvoss, University of Washington, U.S.; Neta Singer, École Polytechnique Fédérale de Lausanne, Switzerland		 Optimal Randomized Clustering for Subsets of $L_p$ When $p>2$
Assaf Naor and Kevin Ren, Princeton University, U.S.		 Tree Embedding in High Dimensions: Dynamic and Massively Parallel
Gramoz Goranci, University of Vienna, Austria; Shaofeng Jiang, Peking University, China; Peter Kiss, University of Vienna, Austria; Qihao Kong and Yi Qian, Peking University, China; Eva Szilagyi, University of Vienna, Austria
3:15 An Optimal Algorithm for Average Distance in Typical Regular Graphs
Alexandros Eskenazis, CNRS and Sorbonne Université, Paris, France; Manor Mendel, Open University of Israel, Israel; Assaf Naor, Princeton University, U.S.		 Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
Mursalin Habib, Rutgers University, U.S.; Vikrant Ashvinkumar, Rutgers University, U.S.; Shashank Srivastava, Institute for Advanced Studies, U.S.		 \#cfg and \#dnnf Admit Fpras
Kuldeep S. Meel, Georgia Institute of Technology, U.S.; Alexis De Colnet, Technische Universität Wien, Austria		 An Optimal Online Algorithm for Robust Flow Time Scheduling
Zhaozi Wang and Anupam Gupta, New York University, U.S.; Amit Kumar, Indian Institute of Technology, Delhi, India; Debmalya Panigrahi, Duke University, U.S.
3:35 A Broader View on Clustering under Cluster-Aware Norm Objectives
Martin G. Herold, MPI Informatik, Germany; Evangelos Kipouridis, Max Planck Institute for Informatics, Germany; Joachim Spoerhase, University of Liverpool, United Kingdom		 Distributed Interactive Proofs for Planarity with Log-Star Communication
Yuval Gil, Reykjavik University, Iceland; Merav Parter, Weizmann Institute of Science, Israel		 Does Block Size Matter in Randomized Block Krylov Low-Rank Approximation?
Raphael A. Meyer, University of California, Berkeley, U.S.; Tyler Chen, New York University, U.S.; Ethan Epperly, University of California, Berkeley, U.S.; Christopher Musco, New York University, U.S.; Akash Rao, Washington State University, U.S.		 Learning Packing and Covering from Samples
Anupam Gupta, New York University, U.S.; Marco Molinaro, Microsoft Research, U.S.
3:55 PMCoffee Break
4:20 PM - 6:00 PM CP9 SODA 3A: Quantum
Regency C - 3rd Floor		 CP10 SODA 3B: Approximation Algorithms
Regency D - 3rd Floor		 CP11 SODA 3C: Algorithmic Game Theory
Plaza B - 2nd Floor		 CP12 SODA 3D: Pattern Matching
Plaza C - 2nd Floor
4:20 Distributed Quantum Advantage in Locally Checkable Labeling Problems
Alkida Balliu, Filippo Casagrande, and Francesco D'Amore, Gran Sasso Science Institute, Italy; Massimo Equi, Barbara Keller, and Henrik Lievonen, Aalto University, Finland; Dennis Olivetti, Gran Sasso Science Institute, Italy; Gustav Schmid, Universität Freiburg, Germany; Jukka Suomela, Aalto University, Finland		 A Better-Than-5/4-Approximation for Two-Edge Connectivity
Felix Hommelsheim, Universidad de Chile, Chile; Alexander Lindermayr, University of California, Berkeley, U.S.; Zhenwei Liu, Zhejiang University, China		 Contextual Search in Principal-Agent Games: The Curse of Degeneracy
Yiding Feng, Hong Kong University of Science and Technology, Hong Kong; Mengfan Ma, Central China Normal University, China; Bo Peng, Shanghai University of Finance and Economics, China; Zongqi Wan, Great Bay University, Dongguan, Guangdong, China		 Tight Lower Bounds for Central String Queries in Compressed Space
Dominik Kempa, Stony Brook University, U.S.; Tomasz Kociumaka, Max-Planck Institute for Informatics, Germany
4:40 Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
Jon Nelson and Joel Rajakumar, University of Maryland, U.S.; Dominik Hangleiter, ETH Zurich, Switzerland; Michael Gullans, University of Maryland, U.S.		 Augmenting Packing Dynamic Programs to Handle (Many) Additional Budget Constraints
Alexander Armbruster, Technische Universität München, Germany; Fabrizio Grandoni and Antoine Tinguely, IDSIA, Switzerland; Andreas Wiese, Technische Universität München, Germany		 Compatibility of Fairness and Nash Welfare under Subadditive Valuations
Siddharth Barman, Indian Institute of Science, India; Mashbat Suzuki, University of New South Wales, Australia		 Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences Between String Problems and Prefix Range Queries
Dominik Kempa, Stony Brook University, U.S.; Tomasz Kociumaka, Max-Planck Institute for Informatics, Germany
5:00 Bounding the Asymptotic Quantum Value of All Multipartite Compiled Non-Local Games
Matilde Baroni, LIP6 and Sorbonne University, France; Dominik Leichtle, University of Edinburgh, United Kingdom; Siniša Jankovic, University of Belgrade, Serbia; Ivan Šupić , Université de Grenoble Alpes, France		 A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
Meike Neuwohner, CNRS & DIENS, ENS Paris - PSL Research University, France; Olha Silina, Carnegie Mellon University, U.S.; Michael Zlatin, Pomona College, U.S.		 Approximately Dominating Sets in Elections
Moses Charikar and Prasanna Ramakrishnan, Stanford University, U.S.; Kangning Wang, Rutgers University, U.S.		 The Complexity of Dynamic Lz77 Is $\tilde{\Theta}(n^{2/3})$
Itai Boneh, University of Wroclaw, Poland; Shay Golan, Ariel University, Israel; Matan Kraus, Bar Ilan University, Israel
5:20 Quantum Advantage Via Solving Multivariate Polynomials
Pierre Briaud, Simula Research Laboratory, Norway; Itai Dinur, Ben Gurion University, Israel; Riddhi Ghosal, University of California, Los Angeles, U.S.; Aayush Jain, Carnegie Mellon University, U.S.; Paul Lou and Amit Sahai, University of California, Los Angeles, U.S.		 Unsplittable Flow Cut Gap in Undirected Graphs
David Aleman Espinosa, University of Waterloo, Canada; Nikhil Kumar, Tata Institute of Fundamental Research, India; Joseph Poremba and Bruce Shepherd, University of British Columbia, Canada		 Likelihood of the Existence of Average Justified Representation
Qishen Han, Rutgers University, U.S.; Biaoshuai Tao, Shanghai Jiao Tong University, China; Lirong Xia and Chengkai Zhang, Rutgers University, U.S.; Houyu Zhou, University of New South Wales, Australia		 Space-Efficient $k$-Mismatch Text Indexes
Jakub Radoszewski, University of Warsaw, Poland; Tomasz Kociumaka, Max-Planck Institute for Informatics, Germany
5:40 Quantum Hamiltonian Certification
Minbo Gao, University of Chinese Academy of Sciences, China; Zhengfeng Ji, Tsinghua University, P. R. China; Qisheng Wang, University of Edinburgh, United Kingdom; Wenjun Yu, University of Hong Kong, China; Qi Zhao, The University of Hong Kong, Hong Kong
Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
Ashwin Padaki, Sanjeev Khanna, and Erik Waingarten, University of Pennsylvania, U.S.
Efficiently Constructing Sparse Navigable Graphs
Alex Conway, Cornell University, U.S.; Laxman Dhulipala, University of Maryland, College Park, U.S.; Martin Farach-Colton, New York University, U.S.; Rob Johnson, Vmware Research, U.S.; Ben Landrum, Cornell Tech University, U.S.; Christopher Musco, Yarin Shechter, and Torsten Suel, New York University, U.S.; Richard Wen, University of Maryland, College Park, U.S.
 Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets
Riccardo Colini-Baldeschi, Meta, U.S.; Sophie Klumper and Twan Kroll, CWI Amsterdam and University of Amsterdam, Netherlands; Stefano Leonardi, Università di Roma "La Sapienza", Italy; Guido Schäfer, CWI Amsterdam and University of Amsterdam, Netherlands; Artem Tsikiridis, Technische Universität München, Germany		 Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
Rajat De and Dominik Kempa, Stony Brook University, U.S.
Monday, January 12
8:30 AMContinental Breakfast
8:30 AMRegistration
9:00 AM - 11:00 AM CP13 SODA 4A: Parameterized Algorithms
Regency C - 3rd Floor		 CP14 SODA 4B:Algorithmic Game Theory
Regency D - 3rd Floor		 CP15 SODA 4C: Algorithmic Graph Theory
Plaza B - 2nd Floor		 CP16 SODA 4D:Randomized/Probabilistic Method
Plaza C - 2nd Floor		 CP46 SOSA Session 1
Plaza A - 2nd Floor
9:00 K-Sum Hardness Implies Treewidth-Seth
Michael Lampis, Université Paris Dauphine, France		 Prophet Inequality from Samples: Is the More the Merrier?
Tomer Ezra, Harvard University, U.S.		 The Directed Disjoint Paths Problem with Congestion
Stephan Kreutzer, Matthias Bentert, Dario Cavallaro, and Amelie Heindl, Technische Universität Berlin, Germany; Ken-ichi Kawarabayashi, National Institute of Informatics, Japan; Johannes Schröder, Technische Universität Berlin, Germany		 A Classical Quadratic Speedup for Planted Kxor
William He, Carnegie Mellon University, U.S.; Meghal Gupta, University of California, Berkeley, U.S.; Noah Singer and Ryan O'Donnell, Carnegie Mellon University, U.S.		 The Road to the Closest Point Is Paved by Good Neighbors
Benjamin A. Raichel, University of Texas at Dallas, U.S.; Sariel Har-Peled and Eliot Robson, University of Illinois Urbana-Champaign, U.S.
9:20 Circuits and Backdoors: Five Shades of the Seth
Michael Lampis, Université Paris Dauphine, France		 Contract Design Beyond Hidden-Actions
Tomer Ezra, Harvard University, U.S.; Stefano Leonardi, Università di Roma "La Sapienza", Italy; Matteo Russo, Università La Sapienza, Rome, Italy		 Disjoint Paths in Expanders in Deterministic Almost-Linear Time Via Hypergraph Perfect Matching
Matija Bucic and Zhongtian He, Princeton University, U.S.; Shang-En Huang, National Taiwan University, Taiwan; Thatchaphol Saranurak, University of Michigan, U.S.		 Efficient Online Random Sampling Via Randomness Recycling
Thomas L. Draper and Feras Saad, Carnegie Mellon University, U.S.		 Redistricting in Triangular and Square Grids
Frederick Stock and Hugo A. Akitaya, University of Massachusetts, Lowell, U.S.; Kyle Dituro and Andrei Gonczi, Tufts University, U.S.; Matias Korman, Siemens Electronic Design Automation, U.S.; Diane Souvaine, Tufts University, U.S.; Csaba D. Toth, California State University, Northridge, U.S.
9:40 The Parameterised Complexity of Counting Small Sub-Hypergraphs
Marc Roth, Oxford University, United Kingdom; Marco Bressan, University of Milan, Italy; Julian Brinkmann and Holger Dell, Goethe University Frankfurt, Germany; Philip Wellnitz, National Institute of Informatics, Japan		 The Communication Complexity of Combinatorial Auctions with Additional Succinct Bidders
Frederick V. Qiu, S. Matthew Weinberg, and Qianfan Zhang, Princeton University, U.S.		 Balanced Spanning Tree Distributions Have Separation Fairness
Harry Chen, Massachusetts Institute of Technology, U.S.; Kamesh Munagala and Govind S. Sankar, Duke University, U.S.		 Explicit Min-Wise Hash Families with Optimal Size
Xue Chen and Shengtang Huang, University of Science and Technology of China, China; Xin Li, Johns Hopkins University, U.S.		 A Simple Schnyder Drawing Algorithm for Cylindric and Toroidal Triangulations, with Grid Size O(n)xO(n)
Luca Castelli Aleardi, École Polytechnique de Paris, France; Giselle Feng, Columbia University, U.S.; Eric Fusy, Université Gustave Eiffel, France
10:00 Augmenting to 4-vertex Connectivity is Fixed-parameter Tractable
Ramanujan M. Sridharan, University of Warwick, United Kingdom; Johannes Carmesin, Technische Universitaet Bergakademie Freiberg, Germany; Jan Kurkofka, Technische Universität Bergakademie Freiberg, Germany		 The Power of Matching for Online Fractional Hedonic Games
Martin Bullinger, University of Bristol, United Kingdom; René Romen and Alexander Schlenga, Technische Universität München, Germany		 A Csp Approach to Graph Sandwich Problems
Santiago Guzmán Pro and Manuel Bodirsky, Technische Universität Dresden, Germany		 On Distributed Colouring of Hyperbolic Random Graphs
Yannic Maus, Technische Universität, Graz, Austria; Janosch Ruff, Hasso Plattner Institute, Germnay		 Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm
Jacobus Conradi, Bonn University, Germany; Ivor van Der Hoog, IT University of Copenhagen, Denmark; Thijs Van Der Horst and Tim Ophelders, TU Eindhoven and Utrecht University, The Netherlands
10:20 Finding Sparse Induced Subgraphs on Graphs of Bounded Induced Matching Treewidth
Hans Bodlaender, University of Utrecht, Netherlands; Fedor Fomin, University of Bergen, Norway; Tuukka Korhonen, University of Copenhagen, Denmark		 Hallucinating Flows for Optimal Mechanisms
Marios Mertzanidis and Athina Terzoglou, Purdue University, U.S.		 Faster Negative Length Shortest Paths by Bootstrapping Hop Reducers
Yufan Huang, Purdue University, U.S.; Peter Jin, University of Illinois Urbana-Champaign, U.S.; Kent Quanrud, Purdue University, U.S.		 Improving Algorithmic Efficiency Using Cryptography: Trapdoored Matrices and Applications
Or Zamir, Tel Aviv University, Israel; Vinod Vaikuntanathan, Massachusetts Institute of Technology, U.S.		 A Levelset Algorithm for 3D-Tarksi
Sebastian Haslebacher and Jonas Lill, ETH Zurich, Switzerland
10:40 A Logic-Based Algorithmic Meta-Theorem for Treedepth: Single Exponential Fpt Time and Polynomial Space
Benjamin Bergougnoux, Aix-Marseille Université, France; Vera Chekan, Humboldt University at Berlin, Germany; Giannos Stamoulis, Université Paris Cité, CNRS, IRIF, France		 Improved Maximin Share Guarantee for Additive Valuations
Ehsan Heidari, Alireza Kaviani, Masoud Seddighin, and Amirmohammad Shahrezaei, Sharif University of Technology, Iran		 Perfect Matchings in Random Sparsifications of Dense Hypergraphs
Jie Han and Jingwen Zhao, Beijing Institute of Technology, China		 Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
Jason Gaitonde, Duke University, U.S.; Elchanan Mossel, Massachusetts Institute of Technology, U.S.		 A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, University of California, Santa Barbara, U.S.; Robert Ganian, Technische Universitaet Wien, Austria; Daniel Lokshtanov and Vaishali Surianarayanan, University of California, Santa Barbara, U.S.
11:00 AMCoffee Break
11:25 AM - 12:25 PM CP SODA Best Paper and Best Student Paper Prize Session
Regency CD - 3rd Floor
11:25 Best Student Paper Award: Online Resource Allocation with Concave, Diminishing-Returns Objectives
Kalen R. Patton, Georgia Institute of Technology, U.S.
11:45 Best Paper Award 1: Existence of Fair and Efficient Allocation of Indivisible Chores
Ryoga Mahara, University of Tokyo, Japan
12:05 Best Paper Award 2: Is Nasty Noise Actually Harder Than Malicious Noise?
Guy Blanc, Stanford University, U.S.; Yizhi Huang, Tal Malkin, and Rocco A. Servedio, Columbia University, U.S.
12:25 PMLunch
1:55 PM - 3:55 PM CP17 SODA 5A: Approximation Algorithms
Regency C - 3rd Floor		 CP18 SODA 5B: Algorithmic Graph Theory
Regency D - 3rd Floor		 CP19 SODA 5C:Combinatorics and Discrete Math
Plaza B - 2nd Floor		 CP20 SODA 5D:Sublinear/Streaming
Plaza C - 2nd Floor		 CP47 SOSA Session 2
Plaza A - 2nd Floor
1:55 Approximating Matroid Basis Testing for Partition Matroids Using Budget-In-Expectation
Lisa Hellerstein, New York University, U.S.; Benedikt M. Plank, Independent Researcher; Kevin Schewior, University of Cologne, Köln, Germany and University of Southern Denmark, Denmark		 New Oracles and Labeling Schemes for Vertex Cut Queries
Asaf Petruschka, Weizmann Institute of Science, Israel; Yonggang Jiang, Max Planck Institute, Germany; Merav Parter, Weizmann Institute of Science, Israel		 Helly-Type Theorems for Splitting Point Sets
Lidor Portal, Ben Gurion University Negev, Israel; Natan Rubin, Ben-Gurion University, Israel		 Spectral Clustering in Birthday Paradox Time
Michael Kapralov, Ekaterina Kochetkova, and Weronika Wrzos-Kaminska, École Polytechnique Fédérale de Lausanne, Switzerland		 Trading Prophets with Initial Capital
Yossi Azar, Niv Buchbinder, Roie Levin, and Or Vardi, Tel Aviv University, Israel
2:15 Smooth Trade-off for Tensor Pca Via Sharp Bounds for Kikuchi Matrices
Jeff Xu, Toyota Technological Institute at Chicago, U.S.		 Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
Simon Meierhans and Maximilian Probst Gutenberg, ETH Zurich, Switzerland; Thatchaphol Saranurak, University of Michigan, U.S.; Wuwei Yuan, ETH Zurich, Switzerland		 On a Clique Game and the Erdos-Hajnal Problem on High-Chromatic High-Girth Subgraphs
Seth Pettie, University of Michigan, U.S.; Gábor Tardos, Renyi Institute, Hungary ; Bartosz Walczak, Jagiellonian University, Poland		 Testing Forbidden Order-Pattern Properties on Hypergrids
Harish Chandramouleeswaran, Chennai Mathematical Institute, India; Ilan I. Newman, Haifa University, Israel; Tomer Pelleg, University of Haifa, Israel; Nithin Varma, University of Cologne, Germany		 The $k$-Fold Matroid Secretary Problem
Rishi Gujjar, Kevin Hua, and Robert Kleinberg, Cornell University, U.S.; Frederick V. Qiu, Princeton University, U.S.
2:35 Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
Omrit Filtser, Tzalik Maimon, and Ofir Yomtovyan, Open University of Israel, Israel		 Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
Jason M. Li and Connor Mowry, Carnegie Mellon University, U.S.; Satish Rao, University of California, Berkeley, U.S.		 Time-Biased Random Walks and Robustness of Expanders
Thomas Sauerwald, University of Cambridge, U.S.; John Sylvester, University of Liverpool, United Kingdom; Sam Olesker Taylor, University of Warwick, United Kingdom		 Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
Nicolas Menand and Erik Waingarten, University of Pennsylvania, U.S.		 Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing
Zongbo Bao, Centrum voor Wiskunde en Informatica (CWI), Netherlands
2:55 Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing
Zachary Friggstad, University of Alberta, Canada; Fabrizio Grandoni and Ramin Mousavi, IDSIA, Switzerland		 An Optimal Density Bound for Discretized Point Patrolling
Ahan Mishra, Cornell University, U.S.		 A Tutte-type Canonical Decomposition of 3- and 4-connected Graphs
Jan Kurkofka and Tim Planken, Technische Universität Bergakademie Freiberg, Germany		 One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
Jelani Nelson, University of California, Berkeley, U.S.; Edith Cohen and Tamas Sarlos, Google Research, U.S.; Mihir Singhal, University of California, Berkeley, U.S.; Uri Stemmer, Tel Aviv University, Israel		 Static Pricing for Single Sample Multi-Unit Prophet Inequalities
Pranav Nuti, University of Chicago, U.S.; Peter Westbrook, Citadel Securities, Switzerland
3:15 Approximate Light Spanners in Planar Graphs
Hung Le, University of Massachusetts, Amherst, U.S.; Shay Solomon, Tel Aviv University, Israel; Cuong Than, University of Massachusetts, Amherst, U.S.; Csaba D. Toth, California State University, Northridge, U.S.; Tianyi Zhang, Nanjing University, China		 Temporal Exploration of Random Spanning Tree Models
Samuel Baguley, Hasso Plattner Institute, Germnay; Andreas Göbel, Universität Potsdam, Germany; Nicolas Klodt and George Skretas, Hasso Plattner Institute, Germnay; John Sylvester and Viktor Zamaraev, University of Liverpool, United Kingdom		 On the Edge Expansion of Random Polytopes
Marcelo Sales and Asaf Ferber, University of California, Irvine, U.S.; Michael Krivelevich and Wojciech Samotij, Tel Aviv University, Israel		 Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, École Polytechnique Fédérale de Lausanne, Switzerland; Cameron Musco, University of Massachusetts, Amherst, U.S.; Kshiteej Sheth, École Polytechnique Fédérale de Lausanne, Switzerland		 Most Juntas Saturate the Hardcore Lemma
Vinayak M. Kumar, University of Texas at Austin, U.S.
3:35
Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
Yossi Azar and Shahar Lewkowicz, Tel Aviv University, Israel
Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, and More General
Varun Suriyanarayana, Cornell University, U.S.; David B. Shmoys, Cornell University, U.S.; William Umboh, University of Melbourne, Australia
 Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter's Threshold Barrier
Zhangsong Li, Guanyi Chen, Jian Ding, and Shuyang Gong, Peking University, China		 Constructive L2-Discrepancy Minimization with Additive Deviations
Kunal Dutta, University of Warsaw, Poland		 Online Learning with Limited Information in the Sliding Window Model
Vladimir Braverman, Johns Hopkins University, U.S.; Sumegha Garg, Rutgers University, U.S.; Chen Wang, Rensselaer Polytechnic Institute, U.S.; David Woodruff, Carnegie Mellon University, U.S.; Samson Zhou, Texas A&M University, U.S.		 An Exact Algorithm for the Unanimous Vote Problem
Feyza Duman Keles and Lisa Hellerstein, New York University, U.S.; Kunal Marwaha, University of Chicago, U.S.; Christopher Musco, New York University, U.S.; Xinchen Yang, University of Maryland, U.S.
3:55 PMCoffee Break
4:20 PM - 6:00 PM CP21 SODA 6A: Quantum
Regency C - 3rd Floor		 CP22 SODA 6B: Approximation Algorithms
Regency D - 3rd Floor		 CP23 SODA 6C: Fine Grained
Plaza B - 2nd Floor		 CP24 SODA 6D:Computational Geometry/Data Structure
Plaza C - 2nd Floor		 CP48 SOSA Session 3
Plaza A - 2nd Floor
4:20 A Post-Quantum Lower Bound for the Distributed Lovász Local Lemma
Tim Göttlicher, Aalto University, Finland; Sebastian Brandt, CISPA Helmholtz Center for Information Security, Germany		 Weighted Pseudorandom Generators for Read-Once Branching Programs Via Weighted Pseudorandom Reductions
Kuan Cheng and Ruiyang Wu, Peking University, China		 A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Weizmann Institute of Science, Israel; Shyan Akmal and Nick Fischer, Max Planck Institute for Informatics, Germany		 A Well-Separated Pair Decomposition for Low Density Graphs
Sampson Wong, University of Copenhagen, Denmark; Joachim Gudmundsson, University of Sydney, Australia		 Continual Release of Densest Subgraphs: Privacy Amplification and Sublinear Space Via Subsampling
Felix Zhou, Yale University, U.S.
4:40 Beating Full State Tomography For Unentangled Spectrum Estimation
Angelos Pelecanos, University of California, Berkeley, U.S.; Xinyu Tan, Massachusetts Institute of Technology, U.S.; Ewin Tang and John Wright, University of California, Berkeley, U.S.
Tree Covers of Size 2 for the Euclidean Plane
Andrey Kupavskii and Artur Bikeev, Moscow Institute of Physics and Technology, Russia; Maksim Turevskii, Saint Petersburg State University, Russia
Covering the Euclidean Plane by a Pair of Trees
Hung Le, University of Massachusetts, Amherst, U.S.; Lazar Milenkovic and Shay Solomon, Tel Aviv University, Israel; Tianyi Zhang, Nanjing University, China
 Derandomizing Pseudopolynomial Algorithms for Subset Sum
Timothy M. Chan, University of Illinois Urbana-Champaign, U.S.		 Dynamic 3D Convex Hulls Revisited and Applications
Haitao Wang, University of Utah, U.S.		 Efficient Derandomization of Differentially Private Counting Queries
Surendra Ghentiyala, Cornell University, U.S.
5:00 On the Quantum Chromatic Gap
Lorenzo Ciardo, Technische Universität, Graz, Austria		 A $(2+\varepsilon)$-Approximation Algorithm for the General Scheduling Problem in Quasipolynomial Time
Alexander Armbruster, Technische Universität München, Germany; Lars Rohwedder, University of Southern Denmark, Denmark; Andreas Wiese, Technische Universität München, Germany		 Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective
Lin Chen, Yuchen Mao, and Guochuan Zhang, Zhejiang University, China		 Computing the Heaviest Disk and Related Problems
Esther Ezra, Bar Ilan University, Israel; Pankaj Agarwal, Duke University, U.S.; Micha Sharir, Tel Aviv University, Israel		 Semi-Robust Communication Complexity of Maximum Matching
Christian Konrad, Gabriel Cipriani Huete, and Adithya Diddapur, University of Bristol, United Kingdom; Pavel Dvorak, Charles University in Prague, Czech Republic
5:20 Quantum State Preparation with Optimal T-Count
Robin Kothari, Google Research, U.S.; David Gosset, University of Waterloo, Canada; Kewen Wu, University of California, Berkeley, U.S.		 $(\alpha, \beta)$-Spanners and Hybrid Spanners with Nearly Tight Bounds
Gur Lifshitz and Shiri Chechik, Tel Aviv University, Israel		 Improved Additive Approximation Algorithms for APSP
Ce Jin, University of California, Berkeley, U.S.; Yael Kirkpatrick, Massachusetts Institute of Technology, U.S.; Michal Stawarz, ETH Zurich, Switzerland; Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.		 Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
William Kuszmaul, Jingxun Liang, and Renfei Zhou, Carnegie Mellon University, U.S.		 A (Very) Nearly Optimal Sketch for $k$-Edge Connectivity Certificates
Pachara Sawettamalya and Huacheng Yu, Princeton University, U.S.
5:40 Rapid Mixing for Gibbs States Within a Logical Sector: a Dynamical View of Self-Correcting Quantum Memories
Thiago Bergamaschi, Massachusetts Institute of Technology, U.S.; Reza Gheissari, Northwestern University, U.S.; Yunchao Liu, Harvard University, U.S.		 Shortcuts and Transitive-Closure Spanners Approximation
Parinya Chalermsook, University of Sheffield, United Kingdom; Yonggang Jiang, Max Planck Institute, Germany; Danupon Nanongkai, Max Planck Institute for Informatics, Germany; Sagnik Mukhopadhyay, University of Birmingham, United Kingdom		 Near-Linear Time Subhypergraph Counting in Bounded Degeneracy Hypergraphs
Daniel Paul-Pena and C. Seshadhri, University of California, Santa Cruz, U.S.		 A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Rasmus Kyng, Maximilian Probst Gutenberg, Weixuan Yuan, and Wuwei Yuan, ETH Zurich, Switzerland		 Simple Average-Case Analysis of Recursive Randomized Greedy Mis
Mina Dalirrooyfard, Morgan Stanley, U.S.; Konstantin Makarychev, Northwestern University, U.S.; Slobodan Mitrovic, University of California, Davis, U.S.
6:15 PMSODA Business Meeting & Awards Presentation, followed by SOSA Business Meeting **Complimentary beer and wine will be served**
Tuesday, January 13
8:30 AMContinental Breakfast
8:30 AMRegistration
9:00 AM - 11:00 AM CP25 SODA 7A: Approximation Algorithms
Regency C - 3rd Floor		 CP26 SODA 7B: Algorithmic Graph Theory
Regency D - 3rd Floor		 CP27 SODA 7C:Randomized/Probabilistic Method
Plaza B - 2nd Floor		 CP28 SODA 7D:Sublinear/Streaming/Distributed Algorithms
Plaza C - 2nd Floor		 CP49 SOSA Session 4
Plaza A - 2nd Floor
9:00 PageRank Centrality in Directed Graphs with Bounded In-Degree
Mikkel Thorup and Hanzhi Wang, University of Copenhagen, Denmark; Zhewei Wei and Mingji Yang, Renmin University of China, China		 Burling Graphs in Graphs with Large Chromatic Number
Tara Abrishami, Stanford University, U.S.; Marcin Brianski, Jagiellonian University, Poland; James Davies, University of Leipzig, Germany; Xiying Du, Georgia Institute of Technology, U.S.; Jana Masaríková and Pawel Rzazewski, University of Warsaw, Poland; Bartosz Walczak, Jagiellonian University, Poland		 Optimal Mass Estimation in the Conditional Sampling Model
Tomer Adar and Eldar Fischer, Technion Israel Institute of Technology, Israel; Amit Levi, University of Haifa, Israel		 Near-Optimal Four-Cycle Counting in Graph Streams
Sebastian Lüderssen and Stefan Neumann, Technische Universität Wien, Austria; Pan Peng, University of Science and Technology of China, China		 A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Harry Buhrman, Quantinuum, U.K.; Sevag Gharibian, Paderborn University, Germany; Zeph Landau, University of California, Berkeley, U.S.; Francois Le Gall, Nagoya University, Japan; Norbert Schuch, University of Vienna, Austria; Suguru Tamaki, University of Hyogo, Japan
9:20 Selfish, Local and Online Scheduling via Vector Fitting
Danish Kashaev, Centrum voor Wiskunde en Informatica, Netherlands		 History-Independent Maximal Matchings can Be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees
Rathish Das, University of Houston, U.S.; William Kuszmaul, Carnegie Mellon University, U.S.		 Dichotomy for Orderings?
Gabor Kun, Hungarian Academy of Sciences, Hungary; Jaroslav Nesetril, Charles University, Czech Republic		 Spectral Clustering with Side Information
Ekaterina Kochetkova, École Polytechnique Fédérale de Lausanne, Switzerland; Hendrik Fichtenberger, Google Research, U.S.; Michael Kapralov, École Polytechnique Fédérale de Lausanne, Switzerland; Silvio Lattanzi, Google Zurich, Switzerland; Davide Mazzali and Weronika Wrzos-Kaminska, École Polytechnique Fédérale de Lausanne, Switzerland		 A Novel Reduction from \#sat to \#2sat Based on Symmetry: Simply Drop the Large Clauses
Erik Demaine, Massachusetts Institute of Technology, U.S.; Max Bannach, European Space Agency, France; Timothy Gomez, Massachusetts Institute of Technology, U.S.; Markus Hecher, CNRS Ecole Centrale Paris, France
9:40 Combinatorial Philosopher Inequalities
Yifan Wang, Georgia Institute of Technology, U.S.; Enze Sun, University of Hong Kong, Hong Kong; Zhihao Gavin Tang, Shanghai University of Finance and Economics, China		 Faster Algorithms for Packing Forests in Graphs and Related Problems
Pavel Arkhipov and Vladimir Kolmogorov, Institute of Science and Technology, Austria		 Weighted $k$-Server Admits An Exponentially Competitive Algorithm
Ashish Chiplunkar, Indian Institute of Technology, Delhi, India; Adithya Bijoy, National University of Singapore, Singapore; Ankit Mondal, Indian Institute of Technology, Delhi, India		 $L_p$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness
Honghao Lin, Carnegie Mellon University, U.S.; Zhao Song, University of California, Berkeley, U.S.; David Woodruff, Carnegie Mellon University, U.S.; Shenghao Xie and Samson Zhou, Texas A&M University, U.S.		 Tight Lower Bound for Multicolor Discrepancy
Pasin Manurangsi, Google Research, Thailand; Raghu Meka, University of California, Los Angeles, U.S.
10:00 Hardness of Approximation for Shortest Path with Vector Costs
Ron Mosenzon, Toyota Technological Institute, U.S.; Charlie Carlson, SUNY College at Buffalo, U.S.; Yury Makarychev, Toyota Technological Institute at Chicago, U.S.		 Sensitivity Lower Bounds for Approximation Algorithms
Yuichi Yoshida, National Institute of Informatics, Japan; Noah Fleming, Lund University, Sweden		 Balls and Bins and the Infinite Process with Random Deletions
Peter Kling, University of Applied Sciences Darmstadt, Germany; Petra Berenbrink, Universität Hamburg, Germany; Tom Friedetzky, Durham University, United Kingdom; Lars Nagel, Loughborough University, United Kingdom		 Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
Hadley Black and Christopher Ye, University of California, San Diego, U.S.		 Simple Length-Constrained Expander Decompositions
Bernhard Haeupler, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Greg Bodwin, University of Michigan, U.S.; Ellis Hershkowitz, Brown University, U.S.; Zihan Tan, Rutgers University, U.S.
10:20 A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
Marc Dufay, ETH Zurich, Switzerland; Roger Wattenhofer, ETH Zurich, Switzerland		 All-Pairs Minimum Cut Using $\tilde{O}(n^{7/4})$ Cut Queries
Yotam Kenneth-Mordoch and Robert Krauthgamer, Weizmann Institute of Science, Israel		 (Almost) Perfect Discrete Iterative Load Balancing
Hamed Hosseinpour and Petra Berenbrink, Universität Hamburg, Germany; Robert Elsaesser, University of Salzburg, Austria; Tom Friedetzky, Durham University, United Kingdom; Dominik Kaaser, Technische Universität Hamburg, Germany; Peter Kling, University of Applied Sciences Darmstadt, Germany; Thomas Sauerwald, University of Cambridge, U.S.		 Faster Distributed Delta-Coloring Via a Reduction to MIS
Yann Bourreau, Sebastian Brandt, and Alexandre Nolin, CISPA Helmholtz Center for Information Security, Germany		 The Sparsification Lemma Via Measure and Conquer
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
10:40 New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
Joshua Brakensiek, University of California, Berkeley, U.S.; Lorenzo Ciardo, Technische Universität, Graz, Austria; Venkatesan Guruswami, University of California, Berkeley, U.S.; Aaron Potechin, University of Chicago, U.S.; Stanislav Zivny, University of Oxford, United Kingdom		 On Independent Spanning Trees in Random Graphs
Keith Frankston, Rutgers University, U.S.; Nemanja Draganic, Oxford University, United Kingdom; Michael Krivelevich, Tel Aviv University, Israel; Alexey Pokrovskiy, University College London, United Kingdom; Liana Yepremyan, Emory University, U.S.		 Phase Transition of the Sinkhorn-Knopp Algorithm
Kun He, Renmin University of China, China		 Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
Shabarish Chenakkod and Michal Derezinski, University of Michigan, U.S.; Xiaoyu Dong, National University of Singapore, Singapore		 A Linear-Time Algorithm for the MCS End-Vertex Problem on Chordal Graphs: A Bonus-Driven Search Strategy
Guozhen Rong and Biao Yuan, Changsha University of Science and Technology, China; Yongjie Yang, Saarland University, Germany; Zhen Zhang, Hunan University, China
11:00 AMCoffee Break
11:25 AMIP2 The Four Color Theorem: Generalizations and Faster Algorithms
Ken-ichi Kawarabayashi (National Institute of Informatics, Japan)
12:25 PMLunch
1:55 PM - 3:55 PM CP29 SODA 8A: Parameterized
Regency C - 3rd Floor		 CP30 SODA 8B: Algorithmic Game Theory
Regency D - 3rd Floor		 CP31 SODA 8C:Combinatorics and Discrete Math
Plaza B - 2nd Floor		 CP32 SODA 8D:Lower Bound + Complexity Theory
Plaza C - 2nd Floor		 CP50 SOSA Session 5
Plaza A - 2nd Floor
1:55 A Parameterized Linear Formulation of the Integer Hull
Friedrich Eisenbrand, École Polytechnique Fédérale de Lausanne, Switzerland; Thomas Rothvoss, University of Washington, U.S.		 Persuasive Calibration
Yiding Feng, Hong Kong University of Science and Technology, Hong Kong; Wei Tang, The Chinese University of Hong Kong, Hong Kong		 On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions
Natan Rubin, Ben-Gurion University, Israel		 Sublinear-Time Lower Bounds for Approximating Matching Size Using Non-Adaptive Queries
Vihan Shah, University of Birmingham, United Kingdom		 Quantum Search on Computation Trees
Jevgenijs Vihrovs, University of Latvia, Latvia
2:15 Planar Disjoint Shortest Paths Is Fixed-Parameter Tractable
Michal Pilipczuk, University of Warsaw, Poland; Giannos Stamoulis, Université Paris Cité, CNRS, IRIF, France; Michal Wlodarczyk, University of Warsaw, Poland		 Nearly Tight Sample Complexity for Matroid Online Contention Resolution
Moran Feldman, University of Haifa, Israel; Ola Svensson, École Polytechnique Fédérale de Lausanne, Switzerland; Rico Zenklusen, ETH Zurich, Switzerland		 Rapid Mixing of Glauber Dynamics for Monotone Systems Via Entropic Independence
Minji Yang and Weiming Feng, University of Hong Kong, China		 On the Universality of Round Elimination Fixed Points
Sebastian Brandt, CISPA Helmholtz Center for Information Security, Germany; Alkida Balliu, Gran Sasso Science Institute, Italy; Ole Gabsdil, CISPA Helmholtz Center for Information Security, Germany; Dennis Olivetti, Gran Sasso Science Institute, Italy; Jukka Suomela, Aalto University, Finland		 Faster Convolutions: Yates and Strassen Revisited
Cornelius Brand, Universität Regensburg, Germany; Radu Curticapean, University of Regensburg, Germany and IT University of Copenhagen, Denmark; Baitian Li, Columbia University, U.S.; Kevin Pratt, New York University, U.S.
2:35 $\cal H$-Planarity and Parametric Extensions: When Modulators Act Globally
Fedor Fomin, Petr Golovach, and Laure Morelle, University of Bergen, Norway; Dimitrios Thilikos, CNRS, LIRMM, France		 Collaborative Prediction: Tractable Information Aggregation Via Agreement
Natalie Collina, University of Pennsylvania, U.S.; Ira Globus-Harris, Cornell University and the University of Pennsylvania, U.S.; Surbhi Goel, Varun Gupta, Aaron Roth, and Mirah Shi, University of Pennsylvania, U.S.		 The Erdos-Pósa Property for Circle Graphs as Vertex-minors
Sebastian Wiederrecht and Rutger Campbell, KAIST, Korea; J. Pascal Gollin, University of Primorska, Slovenia; Meike Hatzel, Technische Universität Darmstadt, Germany; O-Joung Kwon, Hanyang University, South Korea; Rose McCarty, Georgia Institute of Technology, U.S.; Sang-Il Oum, Institute for Basic Science / KAIST, Korea		 Better Bounds for Semi-Streaming Single-Source Shortest Paths
Sepehr Assadi, University of Waterloo, Canada; Gary Hoppenworth, University of Michigan, U.S.; Janani Sundaresan, University of Waterloo, Canada		 Debiasing Polynomial and Fourier Regression
Chris Camano, California Institute of Technology, U.S.; Raphael A. Meyer, University of California, Berkeley, U.S.; Kevin Shu, California Institute of Technology, U.S.
2:55 A Quasi-Polynomial Bound for the Minimal Excluded Minors for a Surface
Sarah Houdaigoui and Ken-ichi Kawarabayashi, National Institute of Informatics, Japan		 Networked Information Aggregation Via Machine Learning
Michael Kearns and Aaron Roth, University of Pennsylvania, U.S.; Emily Ryu, Cornell University, U.S.		 Traversing Regions of Supersolvable Hyperplane Arrangements and Their Lattice Quotients
Sofia Brenner, Universität Kassel, Germany; Jean Cardinal, Université Libre de Bruxelles, Belgium; Thomas McConville, Kennesaw State University, U.S.; Arturo Merino, Universidad de O'Higgins, Chile; Torsten Mütze, Universität Kassel, Germany		 Downward Self-reducibility in the Total Function Polynomial Hierarchy
Karthik Gajulaplli, Georgetown University, U.S.; Surendra Ghentiyala, Cornell University, U.S.; Zeyong Li, National University of Singapore, Singapore; Sidhant Saraogi, Georgetown University, U.S.		 A Note on Ordered Ruzsa-Szemerédi Graphs
Kevin Pratt, New York University, U.S.
3:15 Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
Fedor Fomin and Petr Golovach, University of Bergen, Norway; Tanmay Inamdar, Indian Institute of Technology Jodhpur, India; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Meirav Zehavi, Ben-Gurion University, Israel		 Online Proportional Apportionment
Javier Cembrano, Max Plank Institute, Germany; Jose Correa and Svenja M. Griesbach, Universidad de Chile, Chile; Victor Verdugo, Pontificia Universidad Católica de Chile, Chile		 Nearly Optimal Bounds for Stochastic Online Sorting
Yang Hu, Tsinghua University, P. R. China; Jingxun Liang, Carnegie Mellon University, U.S.		 Computational Barriers for Permutation-Based Problems, and Cumulants of Weakly Dependent Random Variables
Bertrand Even and Christophe Giraud, Université Paris-Saclay, France; Nicolas Verzelen, Université de Montpellier, France		 Tree Violation Distance under Constraints
Debarati Das, Pennsylvania State University, U.S.; Evangelos Kipouridis, Max Planck Institute for Informatics, Germany; Joachim Spoerhase, University of Liverpool, United Kingdom
3:35 Catching Rats in $H$-Minor-Free Graphs
Maximilian Gorsky, Institute for Basic Science, Korea; Giannos Stamoulis, Université Paris Cité, CNRS, IRIF, France; Dimitrios Thilikos, CNRS, LIRMM, France; Sebastian Wiederrecht, KAIST, Korea		 A Few Good Choices
Haoyu Song and Thanh Nguyen, Purdue University, U.S.; Young-San Lin, Melbourne School of Business, Australia		 Universal Connection Schedules for Reconfigurable Networking
Tegan Wilson, Northeastern University, U.S.; Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, and Ruogu Zhang, Cornell University, U.S.		 Plane Vs. Plane Low Degree Test
Silas Richelson and Amey Bhangale, University of California, Riverside, U.S.		 A Simple Geometric Proof of the Optimality of the Sequential Probability Ratio Test for Symmetric Bernoulli Hypotheses
Chirag Pabbaraju, Stanford University, U.S.; Gregory Valiant, Microsoft Research, U.S.; Rishi Verma, Stanford University, U.S.
3:55 PMCoffee Break
4:20 PM - 6:00 PM CP33 SODA 9A: Algebraic Methods
Regency C - 3rd Floor		 CP34 SODA 9B: Approximation Algorithms
Regency D - 3rd Floor		 CP35 SODA 9C: Fine Grained
Plaza B - 2nd Floor		 CP36 SODA 9D: Privacy + Fairness
Plaza C - 2nd Floor		 CP51 SOSA Session 6
Plaza A - 2nd Floor
4:20 Entrywise Approximation for Matrix Inversion and Linear Systems
Mehrdad Ghadiri, Massachusetts Institute of Technology, U.S.; Hoai-An Nguyen and Junzhao Yang, Carnegie Mellon University, U.S.		 Spanning Tree Embeddings Are Not Much Harder Than Hierarchical Partitions
Willem Fletcher and D Ellis Hershkowitz, Brown University, U.S.		 Vizing’s Theorem in Deterministic Almost-Linear Time
Sepehr Assadi, University of Waterloo, Canada; Soheil Behnezhad, Northeastern University, U.S.; Sayan Bhattacharya and Martin Costa, University of Warwick, United Kingdom; Shay Solomon, Tel Aviv University, Israel; Tianyi Zhang, Nanjing University, China		 Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Zongrui Zou, Nanjing University, China; Rishi Chandra and Michael Dinitz, Johns Hopkins University, U.S.; Chenglin Fan, Sorbonne University, France		 Reducing Shortcut and Hopset Constructions to Shallow Graphs
Bernhard Haeupler, ETH Zurich, Switzerland; Yonggang Jiang, Max Planck Institute, Germany; Thatchaphol Saranurak, University of Michigan, U.S.
4:40 Algebraic Closure of Matrix Sets Recognized by 1-Vass
Rida Ait El Manssour, Oxford University, United Kingdom; Mahsa Naraghi, Université de Paris, IRIF, CNRS, France; Mahsa Shirmohammadi, Université Paris Cité, France; James Worrell, University of Oxford, United Kingdom		 Approximating Asymmetric A Priori Tsp Beyond the Adaptivity Gap
Manuel Christalla, ETH Zurich, Switzerland; Luise Puhlmann, Universität Bonn, Germany; Vera Traub, ETH Zurich, Switzerland		 Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
Ron Mosenzon, Toyota Technological Institute, U.S.; Julia Chuzhoy, Toyota Technological Institute at Chicago, U.S.; Ohad Trabelsi, University of Haifa, Israel		 Sample-Efficient Replicable Median in Polynomial Time
Kiarash Banihashem, University of Maryland, U.S.; MohammadHossein Bateni and Hossein Esfandiari, Google Research, U.S.; Samira Goudarzi and MohammadTaghi Hajiaghayi, University of Maryland, U.S.		 Simple Algorithms for Fully Dynamic Edge Connectivity
Yotam Kenneth-Mordoch and Robert Krauthgamer, Weizmann Institute of Science, Israel
5:00 The Division Barrier: Optimal Bounds and Structural Limits in Toom-Cook Interpolation
Roy Nissim, Red Hat, Israel; Oded Schwartz, Hebrew University of Jerusalem, Israel; Yuval Spiizer, Tel Aviv University, Israel		 Additive Approximation Schemes for Low-Dimensional Embeddings
Prashanti Anderson, Massachusetts Institute of Technology, U.S.; Ainesh Bakshi, New York University, U.S.; Samuel Hopkins, Massachusetts Institute of Technology, U.S.		 Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
Mikkel Abrahamsen, University of Copenhagen, Denmark; Sujoy Bhore, IIT Bombay, India; Maike Buchin, Ruhr-Universität Bochum, Germany; Jacobus Conradi, Universität Bonn, Germany; Ce Jin, University of California, Berkeley, U.S.; André Nusser, Université Côte d'Azur and INRIA, France; Carolin Rehs, Technical University of Dortmund, Germany		 On the Structure of Replicable Hypothesis Testers
Anders Aamand, University of Copenhagen, Denmark; Maryam Aliakbarpour, Rice University, U.S.; Justin Y. Chen, Massachusetts Institute of Technology, U.S.; Shyam Narayanan, Citadel Securities, Switzerland; Sandeep Silwal, University of Wisconsin-Madison, U.S.		 Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
Shuyi Yan, University of Copenhagen, Denmark
5:20 On the Complexity of the Skolem Problem at Low Orders
Piotr Bacik, University of Oxford, United Kingdom; Joel Ouaknine, Max Planck Institute for Software Systems, Germany; James Worrell, University of Oxford, United Kingdom		 An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the $k$-Means Problem
Vincent Cohen-Addad, Google Research, U.S.; Fabian Kuhn and Zahra Parsaeian, Universität Freiburg, Germany		 Online Orthogonal Vectors Revisited
Karthik Gajulapalli, Alexander Golovnev, Samuel King, and Sidhant Saraogi, Georgetown University, U.S.		 Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
Kobbi Nissim, Georgetown University, U.S.; Eliad Tsfadia, Bar Ilan University, Israel; Chao Yan, Georgetown University, U.S.		 Directed and Undirected Vertex Connectivity Problems Are Equivalent for Dense Graphs
Olivier Fischer, ETH Zurich, Switzerland; Yonggang Jiang, Max Planck Institute, Germany; Sagnik Mukhopadhyay, University of Birmingham, United Kingdom; Sorrachai Yingchareonthawornchai, Aalto University, Finland
5:40 Optimization Modulo Integer Linear-Exponential Programs
Alessio Mansutti, IMDEA Software Institute, Spain; S Hitarth, Hong Kong University of Science and Technology, Hong Kong; Guruprerana Shabadi, University of Pennsylvania, U.S.		 Max Bisection Might Be Harder to Approximate Than Max Cut
Neng Huang, University of Michigan, U.S.; Joshua Brakensiek, University of California, Berkeley, U.S.; Aaron Potechin, University of Chicago, U.S.; Uri Zwick, Tel Aviv University, Israel		 Separations Between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
Sayan Bhattacharya, University of Warwick, United Kingdom; Aaron Bernstein, Rutgers University, U.S.; Nick Fischer, Max Planck Institute for Informatics, Germany; Peter Kiss, University of Vienna, Austria; Thatchaphol Saranurak, University of Michigan, U.S.		 Matroids Are Equitable
Hannaneh Akrami, Max Planck Institute for Informatics, Germany and Saarland University, Germany; Roshan Raj, Tata Institute of Fundamental Research, Mumbai, India; Laszlo Vegh, University of Bonn, Germany		 Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space
Ziad Ismaili Alaoui, University of Liverpool, United Kingdom; Detlef Plump, University of York, United Kingdom; Sebastian Wild, University of Liverpool, United Kingdom
Wednesday, January 14
8:30 AMContinental Breakfast
8:30 AMRegistration
9:00 AM - 11:00 AM CP37 SODA 10A: Approximation Algorithms
Regency C - 3rd Floor		 CP38 SODA 10B:Algorithmic Graph Theory
Regency D - 3rd Floor		 CP39 SODA 10C:Combinatorics and Discrete Math
Plaza B - 2nd Floor		 CP52 SOSA Session 7
Plaza A - 2nd Floor
9:00 A Near-Complete Resolution of the Exponential-Time Complexity of $k$-opt for the Traveling Salesman Problem
Sophia Heimann, Universität Bonn, Germany; Hung Hoang, Technische Universität Wien, Austria; Stefan Hougardy, Universität Bonn, Germany		 Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Marek Sokolowski, Max Planck Institute for Informatics, Germany; Adam Karczmarz and Wojciech Nadara, University of Warsaw, Poland		 Evasive Sets, Twisted Varieties, and Container-Clique Trees
Jeck Lim, University of Oxford, United Kingdom; Jiaxi Nie, Georgia Institute of Technology, U.S.; Ji Zeng, Alfréd Rényi Institute of Mathematics, Hungary		 Maximal Palindromes in Mpc: Simple and Optimal
Solon P. Pissis, CWI, Amsterdam, Netherlands
9:20 Optimal Rounding for Two-Stage Bipartite Matching
Anders Wikum, Tristan Pollner, and Amin Saberi, Stanford University, U.S.		 Sparsifying Cayley Graphs on Every Group
Jun-Ting Hsieh and Daniel Z. Lee, Massachusetts Institute of Technology, U.S.; SIDHANTH Mohanty, Northwestern University, U.S.; Aaron L. Putterman, Harvard University, U.S.; RACHEL Yun Zhang, Massachusetts Institute of Technology, U.S.		 Listing Faces of Polytopes
Sofia Brenner, Universität Kassel, Germany; Nastaran Behrooznia, University of Warwick, United Kingdom; Arturo Merino, Universidad de O'Higgins, Chile; Torsten Mütze, Christian Rieck, and Francesco Verciani, Universität Kassel, Germany		 A Simple Analysis of Ranking in General Graphs
Tao Yu and Mahsa Derakhshan, Northeastern University, U.S.; Mohammad Roghani, Stanford University, U.S.; Mohammad Saneian, Northeastern University, U.S.
9:40 Approximate Counting of Permutation Patterns
Omri Ben-Eliezer, Technion, Israel; Slobodan Mitrovic, University of California, Davis, U.S.; Pranjal Srivastava, Massachusetts Institute of Technology, U.S.		 Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu and Pravesh Kothari, Princeton University, U.S.; Yang Liu, Carnegie Mellon University, U.S.; Raghu Meka, University of California, Los Angeles, U.S.		 Extended Vc-Dimension, and Radon and Tverberg Type Theorems for Unions of Convex Sets
Shakhar Smorodinsky, Ben-Gurion University, Israel; Noga Alon, Princeton University, U.S.		 A Learning Perspective on Random-Order Covering Problems
Anupam Gupta, New York University, U.S.; Marco Molinaro, Microsoft Research, U.S.; Matteo Russo, Università La Sapienza, Rome, Italy
10:00 Sublinear Metric Steiner Forest Via Maximal Independent Set
Mohammad Roghani, Stanford University, U.S.; Sepideh Mahabadi and Jakub Tarnawski, Microsoft Research, U.S.; Ali Vakilian, Virginia Tech, U.S.		 Coloring Graphs with Few Colors in the Streaming Model
Sepehr Assadi, Janani Sundaresan, and Helia Yazdanyar, University of Waterloo, Canada		 A Near-Optimal Quadratic Goldreich-Levin Algorithm
Jop Briët, Centrum voor Wiskunde en Informatica (CWI), Netherlands; Davi Castro-Silva, University of Cambridge, United Kingdom		 Competitive Online Transportation Simplified
Stephen Arndt and Benjamin Moseley, Carnegie Mellon University, U.S.; Kirk Pruhs, University of Pittsburgh, U.S.; Marc Uetz, University of Twente, Netherlands
10:20 Local Search for Clustering in Almost-Linear Time
Shaofeng Jiang, Peking University, China; YAONAN Jin, Huawei Technologies Co., Ltd., China; Jianing Lou, Peking University, China; Pinyan Lu, Shanghai University of Finance and Economics, China		 Three-Edge-Coloring (Tait Coloring) Cubic Graphs and Nowhere-Zero 4-Flow for Graphs on the Torus
Yuta Inoue, University of Tokyo, Japan; Ken-ichi Kawarabayashi, National Institute of Informatics, Japan; Miyashita Atsuyuki, University of Tokyo, Japan; Bojan Mohar, Simon Fraser University, Canada; Tomohiro Sonobe, National Institute of Informatics, Japan		 Braiding Vineyards
Erin Chambers, University of Notre Dame, U.S.; Christopher Fillmore, Institute of Science and Technology, Austria; Elizabeth Stephenson, Orteliu, Norway; Mathijs Wintraecken, Inria Sophia Antipolis, France		 The Harmonic Policy for Online Buffer Sharing Is $(2 + \ln N)$-Competitive: A Simple Proof
Vamsi Addanki, Purdue University, U.S.; Julien Dallot, Technische Universität Berlin, Germany; Leon Kellerhals, Techniche Universität Clausthal, Germany; Maciej Pacut, Stefan Schmid, and Aleksander Figiel, Technische Universität Berlin, Germany
10:40 Local Gibbs Sampling Beyond Local Uniformity
Chunyang Wang, Hongyang Liu, and Yitong Yin, Nanjing University, China		 Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Max Dupré La Tour and Ndiamé Ndiaye, McGill University, Canada; Manuel Lafond, Universite de Sherbrooke, Canada		 Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models
Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, and Konstantin Sturm, ETH Zurich, Switzerland		 Text Indexing and Pattern Matching with Ephemeral Edits
Solon P. Pissis, CWI, Amsterdam, Netherlands
10:40 Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
Simon Meierhans, Maximilian Probst Gutenberg, and Weixuan Yuan, ETH Zurich, Switzerland
11:00 AMCoffee Break
11:25 AMIP3 Some Incremental Results, and the Future of TCS
Gregory Valiant (Stanford University, U.S.)
12:25 PMLunch
1:55 PM - 3:35 PM CP40 SODA 11A: Algebraic Methods
Regency C - 3rd Floor		 CP41 SODA 11B: Algorithmic Game Theory
Regency D - 3rd Floor		 CP42 SODA 11C: Online Algorithms
Plaza B - 2nd Floor		 CP53 SOSA Session 8
Plaza A - 2nd Floor
1:55 Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
Sagnik Dutta, Max Planck Institute for Informatics, Germany; Markus Bläser, Saarland University, Germany; Gorav Jindal, University of Warsaw, Poland		 When Contracts Get Complex: Information-Theoretic Barriers
Paul Dütting, Google Research, U.S.; Michal Feldman and Yoav Gal-Tzur, Tel Aviv University, Israel; Aviad Rubinstein, Stanford University, U.S.		 Nearly Tight Bounds for the Online Sorting Problem
Yossi Azar, Tel Aviv University, Israel; Debmalya Panigrahi, Duke University, U.S.; Or Vardi, Tel Aviv University, Israel		 A Simple and Fast $(3+\varepsilon)$-Approximation for Constrained Correlation Clustering
Nate Veldt, Texas A&M University, U.S.
2:15 On the Usefulness of Promises
Per Austrin, Johan Håstad, and Björn Martinsson, KTH Royal Institute of Technology, Sweden		 Better Regret Rates in Bilateral Trade Via Sublinear Budget Violation
Anna Lunghi, Matteo Castiglioni, and Alberto Marchesi, Politecnico di Milano, Italy		 Online 3-Taxi on General Metrics
Christian Coester and Tze-Yang Poon, University of Oxford, United Kingdom		 Unsplittable Cost Flows from Unweighted Error-Bounded Variants
Laura Vargas Koch, RTWH Aachen, Germany; Chaitanya Swamy, University of Waterloo, Canada; Vera Traub and Rico Zenklusen, ETH Zurich, Switzerland
2:35 On Deterministically Finding An Element of High Order Modulo a Composite
Ziv Oznovich and Ben Lee Volk, Reichman University, Israel		 Contract Design for Sequential Actions
Tomer Ezra, Harvard University, U.S.; Michal Feldman and Maya Schlesinger, Tel Aviv University, Israel		 Learning in An Echo Chamber: Online Learning with Replay Adversary
Daniil Dmitriev, ETH Zurich, Switzerland; Harald Franck, Carolin Heinzler, and Amartya Sanyal, University of Copenhagen, Denmark		 Approximating Graphic Multi-Path Tsp and Graphic Ordered Tsp
Morteza Alimi, Universität Augsburg, Germany; Niklas Dahlmeier, RTWH Aachen, Germany; Tobias Mömke, Universität Augsburg, Germany; Philipp Pabst and Laura Vargas Koch, RTWH Aachen, Germany
2:55 Numerical Linear Algebra in Linear Space
Yiping Liu, Tsinghua University, P. R. China; Hoai-An Nguyen and Junzhao Yang, Carnegie Mellon University, U.S.		 Robust Equilibria in Shared Resource Allocation Via Strengthening Border's Theorem
David X. Lin, Siddhartha Banerjee, Giannis Fikioris, and Éva Tardos, Cornell University, U.S.		 Online Conformal Prediction with Efficiency Guarantees
Vaidehi Srinivas, Northwestern University, U.S.		 No SDP Needed for Efficiently Recovering Planted Regular Bipartite Graphs
Anand Louis and Rameesh Paul, Indian Institute of Science, Bangalore, India
3:15 Lower Bounds for Csp Hierarchies Through Ideal Reduction
Jonas Conneryd, Lund University, Sweden; Yassine Ghannane, University of Copenhagen, Denmark and Lund University, Sweden; Shuo Pang, University of Bristol, United Kingdom		 Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning
Paritosh Verma, Purdue University, U.S.		 Yet Another Proof That BPP $\subseteq$ PH
Ilya Volkovich, Boston College, U.S.