| All day (8:30 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 7A Grand Ballroom C/D - 2nd Floor Chair: William Umboh (Univ. of Melbourne) | SODA 7B Toulouse - 2nd Floor Mezzanine Chair: Nikhil Bansal (UMich) | SODA 7C Grand Ballroom A - 2nd Floor Chair: Artur Czumaj (Univ. of Warwick) | SOSA 3 St. Charles - 1st Floor Chair: Robert Tarjan (Princeton Univ.) |
|---|---|---|---|---|
| 9:00-9:20 | Improved Bounds for Fully Dynamic Matching Via Ordered Ruzsa-Szemeredi Graphs Sepehr Assadi (Univ. of Waterloo); Sanjeev Khanna (UPenn); Peter Kiss (Univ. of Vienna) | Bounding Romain Bourneuf (Inria-LIP-ENS Lyon); Marcin Pilipczuk (Univ. of Warsaw) | An Analogue of Reed's Conjecture for Digraphs Ken-ichi Kawarabayashi and Lucas Picasarri-Arrieta (National Institute of Informatics) | Multi-Dimensional Approximate Counting Dingyu Wang (Univ. of Michigan) |
| 9:25-9:45 | Matching Composition and Efficient Weight Reduction in Dynamic Matching Aaron Bernstein (Rutgers Univ.); Jiale Chen (Stanford Univ.); Aditi Dudeja (Univ. of Salzburg); Zachary Langley (Rutgers Univ.); Aaron Sidford and Ta-Wei Tu (Stanford Univ.) | The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction Erik Waingarten (UPenn); Moses Charikar (Stanford Univ.) | Weak Coloring Numbers of Minor-Closed Graph Classes Jedrzej Hodor (Jagiellonian Univ.); Hoang La (CNRS, Univ. Paris-Saclay); Piotr Micek (Jagiellonian Univ.); Clément Rambaud (CEPAM - CNRS) | 3sum in Preprocessed Universes: Faster and Simpler Adam Polak (Bocconi Univ.); Shashwat Kasliwal and Pratyush Sharma (IIT Delhi) |
| 9:50-10:10 | New Philosopher Inequalities for Online Bayesian Matching, Via Pivotal Sampling Mark Braverman (Princeton Univ.); Mahsa Derakhshan (Northeastern Univ.); Tristan Pollner and Amin Saberi (Stanford Univ.); David Wajc (Technion Israel Institute of Technology) | Embedding Probability Distributions into Low Dimensional Moses Charikar, Spencer Compton, and Chirag Pabbaraju (Stanford Univ.) | Unique-Neighbor Expanders with Better Expansion for Polynomial-Sized Sets Yeyuan Chen (UMich) | Optimal Prefix-Suffix Queries with Applications Solon P. Pissis (CWI, Amsterdam) |
| 10:15-10:35 | Entropy Regularization and Faster Decremental Matching in General Graphs Jiale Chen, Aaron Sidford, and Ta-Wei Tu (Stanford Univ.) | Highway Dimension: a Metric View Andreas E. Feldmann (Univ. of Sheffield); Arnold Filtser (Bar-Ilan Univ.) | A Coarse Erd\H{o}s-P'{o}sa Theorem Jungho Ahn (Korea Institute for Advanced Study); Jochen Pascal Gollin (Univ. of Primorska); Tony Huynh (Univ. Libre de Bruxelles); O-Joung Kwon (Hanyang Univ.) | Pure Binary Finger Search Trees Gerth S. Brodal and Casper Rysgaard (Aarhus Univ.) |
| 10:40-11:00 | Online Dependent Rounding Schemes for Bipartite Matchings, with Applications Joseph (Seffi) Naor (Technion Israel Institute of Technology); Aravind Srinivasan (Univ. of Maryland); David Wajc (Technion Israel Institute of Technology) | Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares Hongjie Chen, Deepak Narayanan Sridharan, and David Steurer (ETH Zurich) | Planar Graphs in Blowups of Fans Pat Morin (Carleton Univ.) | A Simple Algorithm for Dynamic Carpooling with Recourse Yuval Efron, Shyamal Patel, and Cliff Stein (Columbia Univ.) |
| 11:05 AM - 11:30 AM | Coffee Break | Grand Gallery - 2nd Floor |
|---|---|---|
| 11:30 AM - 12:30 PM | IP2 When and Why do Efficient Algorithms Exist (for Constraint Satisfaction and Beyond)? Venkatesan Guruswami (UC Berkeley) | Grand Ballroom C/D - 2nd Floor |
| 12:30 PM - 2:00 PM | Lunch Break | Attendees on their own |
| Time | SODA 8A Grand Ballroom C/D - 2nd Floor Chair: Mike Dinitz (Johns Hopkins Univ.) | SODA 8B Toulouse - 2nd Floor Mezzanine Chair: Hung Le (UMass Amherst) | SODA 8C Grand Ballroom A - 2nd Floor Chair: Venkat Guruswami (UC Berkeley) | SOSA 4 St. Charles - 1st Floor Chair: Seth Pettie (UMich) |
|---|---|---|---|---|
| 2:00-2:20 | Streaming Algorithms Via Local Algorithms for Maximum Directed Cut Santhoshini Velusamy (Toyota Technological Institute at Chicago); Raghuvansh Saxena (Microsoft Research); Noah Singer (CMU); Madhu Sudan (Harvard Univ.) | A Fast Algorithm for Computing Zigzag Representatives Tamal K. Dey (Purdue Univ.); Tao Hou (Univ. of Oregon); Dmitriy Morozov (Lawrence Berkeley National Laboratory) | Hardness of Counting Small Induced Subgraphs: Fourier vs. Sylow Philip Wellnitz and Simon Döring (Max Planck Institute for Informatics); Dániel Marx (CISPA Helmholtz Center for Information Security); Radu Curticapean (Univ. of Regensburg and IT Univ. of Copenhagen); Daniel Neuen (Max Planck Institute for Informatics) | Bidirectional Dijkstra's Algorithm Is Instance-Optimal Bernhard Haeupler (INSAIT, Sofia Univ.); Richard Hladík (Sofia Univ.); Václav Rozhon (ETH Zurich); Robert Tarjan (Princeton Univ.); Jakub Tetek (INSAIT, Sofia Univ.) |
| 2:25-2:45 | Universal Perfect Samplers for Incremental Streams Dingyu Wang (Univ. of Michigan); Seth Pettie (UMich) | Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes Mook Kwon Jung, Seokyun Kang, and Hee-Kap Ahn (POSTECH) | Maximum Span Hypothesis: A Potentially Weaker Assumption Than Gap-ETH for Parameterized Complexity Karthik C. S. (Rutgers Univ.); Subhash Khot (NYU) | A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path Nick Fischer (INSAIT, Sofia Univ.); Bernhard Haeupler (ETH Zurich); Rustam Latypov (Aalto Univ.); Antti Roeyskoe and Aurelio L. Sulser (ETH Zurich) |
| 2:50-3:10 | Streaming and Communication Complexity of Load-Balancing Via Matching Contractors Sepehr Assadi (Univ. of Waterloo); Aaron Bernstein (Rutgers Univ.); Zach Langley (Rutgers Univ.); Lap Chi Lau and Robert Wang (Univ. of Waterloo) | Partitioning a Polygon Into Small Pieces Mikkel Abrahamsen, Nichlas Rasmussen, and Mads Jensen (Univ. of Copenhagen) | Parameterizing the quantification of CMSO: model checking on minor-closed graph classes Ignasi Sau (CNRS, LIRMM); Giannos Stamoulis (Univ. of Warsaw); Dimitrios Thilikos (CNRS, LIRMM) | Efficient Matroid Intersection Via a Batch-Update Auction Algorithm Joakim Blikstad (KTH Royal Institute of Technology); Ta-Wei Tu (Stanford Univ.) |
| 3:15-3:35 | Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits Yuchen He, Zichun Ye, and Chihao Zhang (Shanghai Jiao Tong Univ.) | Computing the Second and Third Systoles of a Combinatorial Surface Matthijs Ebbens (Univ. of Cologne); Francis Lazarus (Univ. Grenoble) | Losing Treewidth In The Presence Of Weights Michal Wlodarczyk (Univ. of Warsaw) | Trading Prophets: How to Trade Multiple Stocks Optimally Surbhi Rajput, Ashish Chiplunkar, and Rohit Vaish (IIT Delhi) |
| 3:40-4:00 | Near-Optimal Relative Error Streaming Quantile Estimation Via Elastic Compactors Hongxun Wu (UC Berkeley); Elena Gribelyuk, Pachara Sawettamalya, and Huacheng Yu (Princeton Univ.) | An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs Natan Rubin (Ben-Gurion Univ.) | Finding irrelevant vertices in linear time on bounded-genus graphs Petr Golovach (Univ. of Bergen); Stavros Kolliopoulos (National and Kapodistrian Univ. of Athens); Giannos Stamoulis (Univ. of Warsaw); Dimitrios Thilikos (CNRS, LIRMM) | A Simple Lower Bound for Set Agreement in Dynamic Networks Pierre Fraigniaud (Univ. Paris Sud & CNRS); Minh Hang Nguyen (Univ. Paris Cité); Ami Paz (CNRS LISN, Univ. Paris-Saclay) |
| 4:05 PM - 4:30 PM | Coffee Break | Grand Gallery - 2nd Floor |
|---|
| Time | SODA 9A Grand Ballroom C/D - 2nd Floor Chair: William Umboh (Univ. of Melbourne) | SODA 9B Toulouse - 2nd Floor Mezzanine Chair: Seth Pettie (UMich) | SODA 9C Grand Ballroom A - 2nd Floor Chair: Rajmohan Rajaraman (Northeastern Univ.) | SOSA 5 St. Charles - 1st Floor Chair: Tobias Mömke (Univ. Augsburg) |
|---|---|---|---|---|
| 4:30-4:50 | Competitive Strategies to Use "Warm Start" Algorithms with Predictions Avrim Blum (Toyota Technological Institute at Chicago); Vaidehi Srinivas (Northwestern Univ.) | Efficient William Kuszmaul (CMU); Michael Mitzenmacher (Harvard Univ.) | Parks and Recreation: Color Fault-Tolerant Spanners Made Local Asaf Petruschka, Merav Parter, Shay Sapir, and Elad Tzalik (Weizmann Institute of Science) | Simple Combinatorial Construction of the Yijia Chen (Shanghai Jiao Tong Univ.); Yi Feng (Shanghai Univ. of Finance and Economics); Bundit Laekhanukit (Independent Researcher); Yanlin Liu (Ocean Univ. of China) |
| 4:55-5:15 | Online Scheduling Via Gradient Descent for Weighted Flow Time Minimization Qingyun Chen, Sungjin Im, and Aditya Petety (Univ. of California, Merced) | Fast and Simple Sorting Using Partial Information Richard Hladík (Sofia Univ.); Bernhard Haeupler (ETH Zurich); John Iacono (Univ. Libre de Bruxelles); Václav Rozhon (ETH Zurich); Robert Tarjan (Princeton Univ.); Jakub Tetek (INSAIT, Sofia Univ.) | Asynchronous 3-Majority Dynamics with Many Opinions Nobutaka Shimizu (Institute of Science Tokyo); Colin Cooper, Frederik Mallmann-Trenn, and Tomasz Radzik (King's College London); Takeharu Shiraga (Chuo Univ.) | Validating a PTAS for Triangle-Free 2-Matching Yusuke Kobayashi and Takashi Noguchi (Kyoto Univ.) |
| 5:20-5:40 | Stronger Adversaries Grow Cheaper Forests: Online Node-Weighted Steiner Problems Sander Borst (Centrum Wiskunde & Informatica); Marek Elias and Moritz Venzin (Bocconi Univ.) | Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval Aaron L. Putterman (Harvard Univ.); William Kuszmaul (CMU); Tingqiang Xu and Hangrui Zhou (Tsinghua Univ.); Renfei Zhou (CMU) | Sublinear-Round Broadcast Without Trusted Setup Andreea Alexandru (Duality Technologies); Julian Loss (CISPA Helmholtz Center for Information Security); Charalampos Papamanthou (Yale Univ.); Giorgos Tsimos (Univ. of Maryland); Benedikt Wagner (Ethereum Foundation) | Simple Approximation Algorithms for Polyamorous Scheduling Yuriy Biktairov (Univ. of Southern California); Leszek Gasieniec (Univ. of Liverpool); Wanchote Po Jiamjitrak (Univ. of Helsinki); N Namrata and Benjamin Smith (Univ. of Liverpool); Sebastian Wild (Univ. of Marburg) |
| 5:45-6:05 | Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs Benjamin Moseley, Aidin Niaparast, and R. Ravi (CMU) | A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM Peyman Afshani (Aarhus Univ.); Nodari Sitchinava (Univ. of Hawaii at Manoa) | Fully-Distributed Byzantine Agreement in Sparse Networks John Augustine (IIT Mumbai); Fabien Dufoulon (Lancaster Univ.); Gopal Pandurangan (Univ. of Houston) | Spectral Sparsification by Deterministic Discrepancy Walk Lap Chi Lau and Robert Wang (Univ. of Waterloo); Hong Zhou (Fuzhou Univ.) |
| 6:10-6:30 | Unweighted Layered Graph Traversal: Passing a Crown Via Entropy Maximization Romain Cosson (Inria); Xingjian Bai (MIT); Christian Coester (Univ. of Oxford) | Top-K Document Retrieval in Compressed Space Gonzalo Navarro (Univ. of Chile); Yakov Nekrich (Michigan Technological Univ.) | On the Locality of Hall's Theorem Sebastian Brandt (CISPA Helmholtz Center for Information Security); Yannic Maus (Technische Univ. Graz); Ananth Narayanan (CISPA Helmholtz Center for Information Security); Florian Schager (TU Graz); Jara Uitto (Aalto Univ.) | Simple Length-Constrained Minimum Spanning Trees Ellis Hershkowitz and Richard Huang (Brown Univ.) |
| 6:35-6:55 | The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints Sven Jäger (RPTU Kaiserslautern-Landau); Alexander Lindermayr and Nicole Megow (Univ. Bremen) | Faster Two-Dimensional Pattern Matching with Jonas Ellert (ENS Paris Saclay); Pawel Gawrychowski and Adam Gorkiewicz (Univ. of Wroclaw); Tatiana Starikovskaya (École Normale Supérieure Paris) | Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement Pierre Civit (EPFL); Ayaz Dzulfikar and Seth Gilbert (National Univ. of Singapore); Rachid Guerraoui, Jovan Komatovic, and Manuel Vidigueira (EPFL); Igor Zablotchi (Mysten Labs) |
| 7:00 PM - 8:00 PM | Jane Street Estimathon | Astor Ballroom I/II - 2nd Floor |
|---|