| All day (8:00 AM - 5:00 PM) | Registration | Grand Gallery - 2nd Floor |
|---|---|---|
| All day (9:00 AM - 5:00 PM) | Exhibitor Hours | Grand Gallery - 2nd Floor |
| 8:30 AM - 9:00 AM | Continental Breakfast | Grand Gallery - 2nd Floor |
| Time | SODA 1A Grand Ballroom C/D - 2nd Floor Chair: Kent Quanrud (Purdue Univ.) | SODA 1B Toulouse - 2nd Floor Mezzanine Chair: Chandra Chekuri (UIUC) | SODA 1C Grand Ballroom A - 2nd Floor Chair: Bill Kuszmaul (CMU) | ALENEX1 St. Charles - 1st Floor Chair: Kasmir Gabert (Sandia National Laboratories) |
|---|---|---|---|---|
| 9:00-9:20 | Connectivity Labeling Schemes for Edge and Vertex Faults Via Expander Hierarchies Yaowei Long, Seth Pettie, and Thatchaphol Saranurak (UMich) | Beyond 2-Approximation for K-Center in Graphs Yael Kirkpatrick, Ce Jin, and Virginia Vassilevska Williams (MIT); Nicole Wein (UMich) | Relative-Error Monotonicity Testing Tianqi Yang and Xi Chen (Columbia Univ.); Anindya De (UPenn); Yizhi Huang, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio (Columbia Univ.) | Optimal Neighborhood Exploration for Dynamic Independent Sets Jannick Borowitz, Ernestine Großmann, and Christian Schulz (Heidelberg Univ.) |
| 9:25-9:45 | A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs Daniel Paul-Pena and C. Seshadhri (UC Santa Cruz) | Dynamic Consistent Sebastian Forster and Antonis Skarlatos (Univ. of Salzburg) | Nearly Tight Bounds on Testing of Metric Properties Yiqiao Bao (UPenn); Sampath Kannan (UPenn and UC Berkeley); Erik Waingarten (UPenn) | Engineering Fully Dynamic Exact Christian Schulz, Ernestine Großmann, and Henrik Reinstädtler (Heidelberg Univ.); Fabian Walliser |
| 9:50-10:10 | Embedding Planar Graphs into Graphs of Treewidth Hsien-Chih Chang (Dartmouth College); Vincent Cohen-Addad (Google Research); Jonathan Conroy (Dartmouth College); Hung Le (UMass Amherst); Marcin Pilipczuk and Michal Pilipczuk (Univ. of Warsaw) | Clustering to Minimize Cluster-Aware Norm Objectives Martin G. Herold (MPI Informatik); Evangelos Kipouridis (Saarland Univ. and Max Planck Institute for Informatics); Joachim Spoerhase (Univ. of Liverpool) | Lower Bounds for Convexity Testing Xi Chen (Columbia Univ.); Anindya De (UPenn); Shivam Nadimpalli and Rocco A. Servedio (Columbia Univ.); Erik Waingarten (UPenn) | A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order Jonas Sauer (Univ. of Bonn); Arne Beines (Formerly of Argonne National Laboratory); Michael Kaibel, Philip Mayer, and Petra Mutzel (Univ. of Bonn) |
| 10:15-10:35 | Deterministic Edge Connectivity and Max Flow Using Subquadratic Cut Queries Aditya Anand and Thatchaphol Saranurak (UMich); Yunfan Wang (Tsinghua Univ.) | Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation Thanasis Pittas and Ilias Diakonikolas (Univ. of Wisconsin-Madison); Daniel Kane (UC San Diego); Jasper Lee (UC Davis) | Tight Sampling Bounds for Eigenvalue Approximation William J. Swartworth and David Woodruff (CMU) | Parallel Cluster-BFS and Applications to Shortest Paths Letong Wang (UC Riverside); Guy Blelloch (CMU); Yan Gu and Yihan Sun (UC Riverside) |
| 10:40-11:00 | Massively Parallel Minimum Spanning Tree in General Metric Spaces Amir Azarmehr and Soheil Behnezhad (Northeastern Univ.); Rajesh Jayaram and Jakub Lacki (Google Research); Vahab Mirrokni (Google, Inc.); Peilin Zhong (Google Research) | Breaking the Two Approximation Barrier for Various Consensus Clustering Problems Debarati Das (Pennsylvania State Univ.); Amit Kumar (IIT Delhi) | Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching Tomasz Kociumaka (Max Planck Institute for Informatics); Jakob Nogler (ETH Zurich); Philip Wellnitz (Max Planck Institute for Informatics) |
| 11:05 AM - 11:30 AM | Coffee Break | Grand Gallery - 2nd Floor |
|---|---|---|
| 11:30 AM - 12:30 PM | IP1 Fully Dynamic Matching, Matching Sparsifiers, and (Ordered) Ruzsa-Szemerédi Graphs Sanjeev Khanna (UPenn) | Grand Ballroom C/D - 2nd Floor |
| 12:30 PM - 2:00 PM | Luncheon (ticketed event) | Astor Ballroom - 2nd Floor |
| Time | SODA 2A Grand Ballroom C/D - 2nd Floor Chair: Chandra Chekuri (UIUC) | SODA 2B Toulouse - 2nd Floor Mezzanine Chair: Soheil Behnezhad (Northeastern Univ.) | SODA 2C Grand Ballroom A - 2nd Floor Chair: Bundit Laekhanukit (Independent Researcher) | ALENEX2 St. Charles - 1st Floor Chair: Christian Schulz (Heidelberg Univ.) |
|---|---|---|---|---|
| 2:00-2:20 | A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints Jesper Nederlof (Utrecht Univ.); Céline Swennenhuis (Univ. of Utrecht); Karol Wegrzycki (Saarland Univ. and Max Planck Institute for Informatics) | Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity Tijn De Vos (Univ. of Salzburg); Aleksander Christiansen (Technical Univ. of Denmark) | Quartic Quantum Speedups for Planted Inference Alexander Schmidhuber (MIT); Ryan O'Donnell (CMU); Robin Kothari and Ryan Babbush (Google Research) | Graph Neural Networks As Ordering Heuristics for Parallel Graph Coloring Kenneth Langedal and Fredrik Manne (Univ. of Bergen) |
| 2:25-2:45 | Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs Shi Li (Nanjing Univ.) | Fully Dynamic Approximate Minimum Cut in Subpolynomial Time Per Operation Jason M. Li (CMU); Antoine El-Hayek (Institute of Science and Technology); Monika Henzinger (Institute of Science and Technology Austria) | Triply Efficient Shadow Tomography Robbie King (California Institute of Technology); David Gosset (Univ. of Waterloo); Robin Kothari and Ryan Babbush (Google Research) | Discrete Transforms of Quantized Persistence Diagrams Vadim Lebovici (Université Sorbonne Paris Nord); Matteo Palo (ETH Zurich); Olympio Hacquard (Kyoto Univ.); Michael E. Van Huffel (ETH Zurich) |
| 2:50-3:10 | Lift-and-Project Integrality Gaps for Santa Claus Etienne Bamas (ETH Zurich) | Fully Dynamic Algorithms for Graph Spanners Via Low-Diameter Router Decomposition Julia Chuzhoy (Toyota Technological Institute at Chicago); Merav Parter (Weizmann Institute of Science) | On Estimating the Trace of Quantum State Powers Yupan Liu (Nagoya Univ.); Qisheng Wang (Univ. of Edinburgh) | Scalable Multilevel and Memetic Signed Graph Clustering Felix Hausberger, Marcelo Fonseca Faraj, and Christian Schulz (Heidelberg Univ.) |
| 3:15-3:35 | The Submodular Santa Claus Problem Etienne Bamas (ETH Zurich); Sarah Morell (Technische Univ. Berlin); Lars Rohwedder (Maastricht Univ.) | Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in- Anton Bukov, Shay Solomon, and Tianyi Zhang (Tel Aviv Univ.) | A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix Yanlin Chen (CWI and QuSoft); Andras Gilyen (Rényi Institute of Mathematics); Ronald de Wolf (CWI Amsterdam and Univ. of Amsterdam) | Batched K-Mer Lookup on the Spectral Burrows-Wheeler Transform Simon J. Puglisi, Jarno Alanko, and Elena Biagi (Univ. of Helsinki); Joel Mackenzie (Univ. of Queensland) |
| 3:40-4:00 | A Tight ( Franziska Eberle (Technische Univ. Berlin); Felix Hommelsheim (Univ. of Bremen); Malin Rau (Chalmers Univ. of Technology); Stefan Walzer (Karlsruhe Institute of Technology) | Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams Janani Sundaresan and Sepehr Assadi (Univ. of Waterloo); Soheil Behnezhad (Northeastern Univ.); Christian Konrad and Kheeran K. Naidu (Univ. of Bristol) | Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth Joel Rajakumar, James Watson, and Yi-Kai Liu (Univ. of Maryland) |
| 4:05 PM - 4:30 PM | Coffee Break | Grand Gallery - 2nd Floor |
|---|
| Time | SODA 3A Grand Ballroom C/D - 2nd Floor Chair: Kent Quanrud (Purdue Univ.) | SODA 3B Toulouse - 2nd Floor Mezzanine Chair: Kangning Wang (Stanford Univ.) | SODA 3C Grand Ballroom A - 2nd Floor Chair: Seth Pettie (UMich) | ALENEX3 St. Charles - 1st Floor Chair: Martin Seybold (Univ. of Vienna) |
|---|---|---|---|---|
| 4:30-4:50 | Lipschitz Continuous Algorithms for Covering Problems Soh Kumabe (CyberAgent, Inc.); Yuichi Yoshida (National Institute of Informatics) | New Prophet Inequalities Via Poissonization and Sharding Elfarouk Harb (Univ. of Illinois at Chicago) | Fixed-Parameter Tractability of Hedge Cut Fedor Fomin and Petr Golovach (Univ. of Bergen); Tuukka Korhonen (Univ. of Copenhagen); Daniel Lokshtanov (UC Santa Barbara); Saket Saurabh (Institute of Mathematical Sciences and Univ. of Bergen) | Linear Assignment on Tile-Centric Accelerators: Redesigning Hungarian Algorithm on IPUs Cheng Huang (Aarhus Univ.); Alexander Mathiasen (Independent Researcher); Josef Dean (Graphcore); Johannes Langguth (Simula Research Laboratory); Davide Mottin and Ira Assent (Aarhus Univ.) |
| 4:55-5:15 | Approximately Counting Knapsack Solutions in Subquadratic Time Weiming Feng (ETH Zurich); Ce Jin (MIT) | Prophet Inequalities: Competing with the Top Mathieu Molina, Nicolas Gast, and Patrick Loiseau (Inria); Vianney Perchet (ENSAE ParisTech) | Crossing Number in Slightly Superexponential Time Jie Xue (NYU-Shanghai); Daniel Lokshtanov (UC Santa Barbara); Fahad Panolan (Univ. of Leeds); Saket Saurabh (Institute of Mathematical Sciences and Univ. of Bergen); Roohani Sharma (Univ. of Bergen); Meirav Zehavi (Ben-Gurion Univ.) | Spiderdan: Matching Augmentation in Demand-Aware Networks Aleksander Figiel, Darya Melnyk, André Nichterlein, Arash Pourdamghani, and Stefan Schmid (Technische Univ. Berlin) |
| 5:20-5:40 | Balancing Notions of Equity: Trade-Offs Between Fair Portfolio Sizes and Achievable Guarantees Swati Gupta (MIT); Jai Moondra and Mohit Singh (Georgia Institute of Technology) | New Combinatorial Insights for Monotone Apportionment Javier Cembrano (Max Planck Institute); Jose Correa (Univ. of Chile); Ulrike Schmidt-Kraepelin (Eindhoven Univ. of Technology); Alexandros Tsigonias-Dimitriadis (European Central Bank); Victor Verdugo (Pontificia Univ. Católica de Chile) | Packing Short Cycles Matthias Bentert, Fedor Fomin, and Petr Golovach (Univ. of Bergen); Tuukka Korhonen (Univ. of Copenhagen); William Lochet (CNRS); Fahad Panolan (Univ. of Leeds); M. S. Ramanujan (Univ. of Warwick); Saket Saurabh (Institute of Mathematical Sciences and Univ. of Bergen); Kirill Simonov (Technische Univ. Wien) | Exploring the Landscape of Distributed Graph Sketching David Tench (Lawrence Berkeley National Laboratory); Evan West (Stony Brook Univ.); Kenny Zhang (UMich); Michael A. Bender and Daniel Delayo (Stony Brook Univ.); Martin Farach-Colton (Rutgers Univ.); Gilvir Gill (Stony Brook Univ.); Tyler Seip (MongoDB); Victor Zhang (Meta Platforms, Inc.) |
| 5:45-6:05 | Approximating Traveling Salesman Problems Using a Bridge Lemma Tobias Mömke (Univ. of Augsburg); Martin Böhm (Univ. of Wroclaw); Zachary Friggstad (Univ. of Alberta); Joachim Spoerhase (Univ. of Liverpool) | Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint Prommy Sultana Hossain (George Mason Univ.); Xintong Wang (Rutgers Univ.); Fang-Yi Yu (George Mason Univ.) | Unbreakable Decomposition in Close-to-Linear Time Aditya Anand and Euiwoong Lee (UMich); Jason M. Li (CMU); Yaowei Long and Thatchaphol Saranurak (UMich) | The Constrained Layer Tree Problem and Applications to Solar Farm Cabling Thomas Bläsius, Max Göttlicher, Sascha Gritzbach, and Wendy Yi (Karlsruhe Institute of Technology) |
| 6:10-6:30 | Min-CSPs on Complete Instances Aditya Anand and Euiwoong Lee (UMich); Amatya Sharma (UMich) | An Elementary Predictor Obtaining Eshwar Ram Arunachaleswaran, Natalie Collina, Aaron Roth, and Mirah Shi (UPenn) | The Primal Pathwidth Seth Michael Lampis (Université Paris Dauphine) | |
| 6:35-6:55 | Constraint Satisfaction Problems with Advice Suprovat Ghoshal (Northwestern Univ.); Konstantin Makarychev (Northwestern Univ.); Yury Makarychev (Toyota Technological Institute at Chicago) | Prophet Secretary and Matching: the Significance of the Largest Item Ziyun Chen (Univ. of Washington); Zhiyi Huang and Dongchen Li (Univ. of Hong Kong); Zhihao Tang (Shanghai Univ. of Finance and Economics) | Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities Vaishali Surianarayanan and Daniel Lokshtanov (UC Santa Barbara); Abhishek Sahu (Homi Bhabha National Institute); Saket Saurabh (Institute of Mathematical Sciences and Univ. of Bergen); Jie Xue (NYU-Shanghai) |
| 6:15 PM - 7:00 PM | ALENEX Business Meeting | St. Charles - 1st Floor |
|---|