| 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, 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 k-Center Clustering with Optimal Recourse Sebastian Forster and Antonis Skarlatos (Univ. of Salzburg) | Nearly Tight Bounds on Testing of Metric Properties Yiqiao Bao, 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 O(log³ n) 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 (Max Planck Institute for Informatics); 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 (Univ. of California, Riverside); Guy Blelloch (CMU); Yan Gu and Yihan Sun (Univ. of California, 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: Soheil Behnezad (Northeastern Univ.) | SODA 2B Toulouse - 2nd Floor Mezzanine Chair: Bundit Laekhanukit (Independent Researcher) | SODA 2C Grand Ballroom A - 2nd Floor Chair: Chandra Chekuri (UIUC) | 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 (Univ. of Utrecht), 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 (Google Research), 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 (Caltech), David Gosset (Univ. of Waterloo), Robin Kothari (Google Research), Ryan Babbush (Google Research) | Discrete Transforms of Quantized Persistence Diagrams Vadim Lebovici (Univ. 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 (TU Berlin), Lars Rohwedder (Maastricht Univ.) | Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier Anton Bukov (Tel Aviv Univ.), Shay Solomon (Tel Aviv Univ.), 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 (3/2 + ε)-Approximation Algorithm for Demand Strip Packing Franziska Eberle (TU 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 (Univ. of Waterloo), Sepehr Assadi (Univ. of Waterloo), Soheil Behnezhad (Northeastern Univ.), Christian Konrad (Univ. of Bristol), Kheeran K. Naidu (Univ. of Bristol) | Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth Joel Rajakumar (Univ. of Maryland), James Watson (Univ. of Maryland), 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 (Univ. of Bergen), 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 (Inria), Nicolas Gast (Inria), 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 (TU Berlin) |
| 5:20-5:40 | Balancing Notions of Equity: Trade-Offs Between Fair Portfolio Sizes and Achievable Guarantees Swati Gupta (MIT), Jai Moondra (Georgia Tech), Mohit Singh (Georgia Tech) | New Combinatorial Insights for Monotone Apportionment Javier Cembrano (Max Planck Institute), Jose Correa (Univ. of Chile), Ulrike Schmidt-Kraepelin (TU Eindhoven), Alexandros Tsigonias-Dimitriadis (European Central Bank), Victor Verdugo (Pontificia Univ. Católica de Chile) | Packing Short Cycles Matthias Bentert (Univ. of Bergen), Fedor Fomin (Univ. of Bergen), 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 (TU Wien) | Exploring the Landscape of Distributed Graph Sketching David Tench (Lawrence Berkeley National Laboratory); Evan West, Kenny Zhang, Michael A. Bender, Daniel Delayo, Gilvir Gill (Stony Brook Univ.); Martin Farach-Colton (Rutgers 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 (UMich), Euiwoong Lee (UMich), Jason M. Li (CMU), Yaowei Long (UMich), 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 (UMich), Euiwoong Lee (UMich), Amatya Sharma (UMich, Ann Arbor) | An Elementary Predictor Obtaining Eshwar Ram Arunachaleswaran (UPenn), Natalie Collina (UPenn), Aaron Roth (UPenn), Mirah Shi (UPenn) | The Primal Pathwidth Seth Michael Lampis (Univ. of Paris Dauphine) |
| 6:15 PM - 7:00 PM | ALENEX Business Meeting | St. Charles - 1st Floor |
|---|