Continental Breakfast
8:30 AM - 9:00 AM |
|
SODA Session 1A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Kent Quanrud | SODA Session 1B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Chandra Chekuri | SODA Session 1C
Room: Grand Ballroom A - 2nd Floor
Chair: Bill Kuszmaul | ALENEX Session 1
Room: St. Charles - 1st Floor
Chair: Kasmir Gabert |
9:00-9:20 Connectivity Labeling Schemes for Edge and Vertex Faults Via Expander Hierarchies
Yaowei Long,
Seth Pettie, and
Thatchaphol Saranurak, University of Michigan, U.S.
| 9:00-9:20 Beyond 2-Approximation for K-Center in Graphs
Yael Kirkpatrick,
Ce Jin, and
Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.; Nicole Wein, University of Michigan, U.S.
| 9:00-9:20 Relative-Error Monotonicity Testing
Tianqi Yang and
Xi Chen, Columbia University, U.S.; Anindya De, University of Pennsylvania, U.S.; Yizhi Huang,
Yuhao Li,
Shivam Nadimpalli, and
Rocco A. Servedio, Columbia University, U.S.
| 9:00-9:20 Optimal Neighborhood Exploration for Dynamic Independent Sets
Jannick Borowitz,
Ernestine Großmann, and
Christian Schulz, Heidelberg University, Germany
|
9:25-9:45 A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs
Daniel Paul-Pena and
C. Seshadhri, University of California, Santa Cruz, U.S.
| 9:25-9:45 Dynamic Consistent $k$-Center Clustering with Optimal Recourse
Sebastian Forster and
Antonis Skarlatos, University of Salzburg, Austria
| 9:25-9:45 Nearly Tight Bounds on Testing of Metric Properties
Yiqiao Bao, University of Pennsylvania, U.S.; Sampath Kannan, University of Pennsylvania and University of California, Berkeley, U.S.; Erik Waingarten, University of Pennsylvania, U.S.
| 9:25-9:45 Engineering Fully Dynamic Exact $\Delta$-Orientation Algorithms
Christian Schulz,
Ernestine Großmann, and
Henrik Reinstädtler, Heidelberg University, Germany; Fabian Walliser,
|
9:50-10:10 Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
Hsien-Chih Chang, Dartmouth College, U.S.; Vincent Cohen-Addad, Google Research, U.S.; Jonathan Conroy, Dartmouth College, U.S.; Hung Le, University of Massachusetts, Amherst, U.S.; Marcin Pilipczuk and
Michal Pilipczuk, University of Warsaw, Poland
| 9:50-10:10 Clustering to Minimize Cluster-Aware Norm Objectives
Martin G. Herold, MPI Informatik, Germany; Evangelos Kipouridis, Saarland University and Max Planck Institute for Informatics, Germany; Joachim Spoerhase, University of Liverpool, United Kingdom
| 9:50-10:10 Lower Bounds for Convexity Testing
Xi Chen, Columbia University, U.S.; Anindya De, University of Pennsylvania, U.S.; Shivam Nadimpalli and
Rocco A. Servedio, Columbia University, U.S.; Erik Waingarten, University of Pennsylvania, U.S.
| 9:50-10:10 A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
Jonas Sauer and
Jonas Sauer, University of Bonn, Germany; Arne Beines, Formerly of Argonne National Laboratory, U.S.; Michael Kaibel, Universität Bonn, Germany; Philip Mayer, Universitaet Bonn, Germany; Petra Mutzel, Universität Bonn, Germany
|
10:15-10:35 Deterministic Edge Connectivity and Max Flow Using Subquadratic Cut Queries
Aditya Anand and
Thatchaphol Saranurak, University of Michigan, U.S.; Yunfan Wang, Tsinghua University, China
| 10:15-10:35 Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
Thanasis Pittas and
Ilias Diakonikolas, University of Wisconsin-Madison, U.S.; Daniel Kane, University of California, San Diego, U.S.; Jasper Lee, University of California, Davis, U.S.
| 10:15-10:35 Tight Sampling Bounds for Eigenvalue Approximation
William J. Swartworth and
David Woodruff, Carnegie Mellon University, U.S.
| 10:15-10:35 Parallel Cluster-BFS and Applications to Shortest Paths
Letong Wang, University of California, Riverside, U.S.; Guy Blelloch, Carnegie Mellon University, U.S.; Yan Gu and
Yihan Sun, University of California, Riverside, U.S.
|
10:40-11:00 Massively Parallel Minimum Spanning Tree in General Metric Spaces
Amir Azarmehr and
Soheil Behnezhad, Northeastern University, U.S.; Rajesh Jayaram and
Jakub Lacki, Google Research, U.S.; Vahab Mirrokni, Google, Inc., U.S.; Peilin Zhong, Google Research, U.S.
| 10:40-11:00 Breaking the Two Approximation Barrier for Various Consensus Clustering Problems
Debarati Das, Pennsylvania State University, U.S.; Amit Kumar, Indian Institute of Technology, Delhi, India
| 10:40-11:00 Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
Tomasz Kociumaka, Max Planck Institute for Informatics, Germany; Jakob Nogler, ETH Zurich, Switzerland; Philip Wellnitz, Max Planck Institute for Informatics, Germany
| |
|
Coffee Break
11:05 AM - 11:30 AM |
|
IP1 Fully Dynamic Matching, Matching Sparsifiers, and (Ordered) Ruzsa-Szemer\'edi Graphs
Room: Grand Ballroom C/D - 2nd Floor
Chair: SIAM Conference Participation System
11:30 AM - 12:30 PM |
|
Luncheon **ticketed event**
12:30 PM - 2:00 PM |
|
SODA Session 2A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Chandra Chekuri | SODA Session 2B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Soheil Behnezad | SODA Session 2C
Room: Grand Ballroom A - 2nd Floor
Chair: Bundit Laekhanukit | ALENEX Session 2
Room: St. Charles - 1st Floor
Chair: Christian Schulz |
2:00-2:20 A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
Jesper Nederlof, Utrecht University, Netherlands; Céline Swennenhuis, University of Utrecht, Netherlands; Karol Wegrzycki, Saarland University and Max Planck Institute for Informatics, Germany
| 2:00-2:20 Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
Tijn De Vos, University of Salzburg, Austria; Aleksander Christiansen, Technical University of Denmark, Denmark
| 2:00-2:20 Quartic Quantum Speedups for Planted Inference
Alexander Schmidhuber, Massachusetts Institute of Technology, U.S.; Ryan O'Donnell, Carnegie Mellon University, U.S.; Robin Kothari and
Ryan Babbush, Google Research, U.S.
| 2:00-2:20 Graph Neural Networks As Ordering Heuristics for Parallel Graph Coloring
Kenneth Langedal and
Fredrik Manne, University of Bergen, Norway
< |
2:25-2:45 Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
Shi Li, Nanjing University, China
| 2:25-2:45 Fully Dynamic Approximate Minimum Cut in Subpolynomial Time Per Operation
Jason M. Li, Carnegie Mellon University, U.S.; Antoine El-Hayek, Institute of Science and Technology, Austria; Monika Henzinger, Institute of Science and Technology Austria, Austria
| 2:25-2:45 Triply Efficient Shadow Tomography
Robbie King, California Institute of Technology, U.S.; David Gosset, University of Waterloo, Canada; Robin Kothari and
Ryan Babbush, Google Research, U.S.
| 2:50-3:10 Scalable Multilevel and Memetic Signed Graph Clustering
|
2:50-3:10 Lift-and-Project Integrality Gaps for Santa Claus
Etienne Bamas, ETH Zurich, Switzerland
| 2:50-3:10 Fully Dynamic Algorithms for Graph Spanners Via Low-Diameter Router Decomposition
Julia Chuzhoy, Toyota Technological Institute at Chicago, U.S.; Merav Parter, Weizmann Institute of Science, Israel
| 2:50-3:10 On Estimating the Trace of Quantum State Powers
Yupan Liu, Nagoya University, Japan; Qisheng Wang, University of Edinburgh, United Kingdom
| 2:50-3:10 Scalable Multilevel and Memetic Signed Graph Clustering
Felix Hausberger,
Marcelo Fonseca Faraj, and
Christian Schulz, Heidelberg University, Germany
|
3:15-3:35 The Submodular Santa Claus Problem
Etienne Bamas, ETH Zurich, Switzerland; Sarah Morell, Technische Universität Berlin, Germany; Lars Rohwedder, Maastricht University, Netherlands
| 3:15-3:35 Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
Anton Bukov,
Shay Solomon, and
Tianyi Zhang, Tel Aviv University, Israel
| 3:15-3:35 A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
Yanlin Chen, CWI and QuSoft, Taiwan; Andras Gilyen, Rényi Institute of Mathematics, Budapest; Ronald de Wolf, CWI Amsterdam and University of Amsterdam, Netherlands
| 3:15-3:35 Batched K-Mer Lookup on the Spectral Burrows-Wheeler Transform
Simon J. Puglisi,
Jarno Alanko, and
Elena Biagi, University of Helsinki, Finland; Joel Mackenzie, University of Queensland, Australia
|
3:40-4:00 A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
Franziska Eberle, Technische Universität Berlin, Germany; Felix Hommelsheim, Universität Bremen, Germany; Malin Rau, Chalmers University of Technology, Sweden; Stefan Walzer, Karlsruhe Institute of Technology, Germany
| 3:40-4:00 Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Janani Sundaresan and
Sepehr Assadi, University of Waterloo, Canada; Soheil Behnezhad, Northeastern University, U.S.; Christian Konrad and
Kheeran K. Naidu, University of Bristol, United Kingdom
| 3:40-4:00 Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
Joel Rajakumar,
James Watson, and
Yi-Kai Liu, University of Maryland, U.S.
| |
|
Coffee Break
4:05 PM - 4:30 PM |
|
SODA Session 3A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Kent Quanrud | SODA Session 3B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Kangning Wang | SODA Session 3C
Room: Grand Ballroom A - 2nd Floor
Chair: Seth Pettie | ALENEX Session 3
Room: St. Charles - 1st Floor
Chair: Martin Seybold |
4:30-4:50 Lipschitz Continuous Algorithms for Covering Problems
Soh Kumabe, CyberAgent, Inc., Japan; Yuichi Yoshida, National Institute of Informatics, Japan
| 4:30-4:50 New Prophet Inequalities Via Poissonization and Sharding
Elfarouk Harb, University of Illinois at Chicago, U.S.
| 4:30-4:50 Fixed-Parameter Tractability of Hedge Cut
Fedor Fomin and
Petr Golovach, University of Bergen, Norway; Tuukka Korhonen, University of Copenhagen, Denmark; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway
| 4:30-4:50 Linear Assignment on Tile-Centric Accelerators: Redesigning Hungarian Algorithm on IPUs
Cheng Huang, Aarhus University, Denmark; Alexander Mathiasen, Independent Researcher; Josef Dean, Graphcore, U.S.; Johannes Langguth, Simula Research Laboratory, Norway; Davide Mottin and
Ira Assent, Aarhus University, Denmark
|
4:55-5:15 Approximately Counting Knapsack Solutions in Subquadratic Time
Weiming Feng, ETH Zurich, Switzerland; Ce Jin, Massachusetts Institute of Technology, U.S.
| 4:55-5:15 Prophet Inequalities: Competing with the Top $\ell$ Items Is Easy
Mathieu Molina,
Nicolas Gast, and
Patrick Loiseau, Inria, France; Vianney Perchet, ENSAE ParisTech, France
| 4:55-5:15 Crossing Number in Slightly Superexponential Time
Jie Xue, New York University-Shanghai, China; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Fahad Panolan, University of Leeds, United Kingdom; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Roohani Sharma, University of Bergen, Norway; Meirav Zehavi, Ben-Gurion University, Israel
| 4:55-5:15 Engineering Optimal Parallel Task Scheduling
Matthew Akram,
Nikolai Maas,
Peter Sanders,
Dominik Schreiber, and
Wendy Yi, Karlsruhe Institute of Technology, Germany; Jonas Sauer and
Jonas Sauer, University of Bonn, Germany
|
5:20-5:40 Balancing Notions of Equity: Trade-Offs Between Fair Portfolio Sizes and Achievable Guarantees
Swati Gupta, Massachusetts Institute of Technology, U.S.; Jai Moondra and
Mohit Singh, Georgia Institute of Technology, U.S.
| 5:20-5:40 New Combinatorial Insights for Monotone Apportionment
Javier Cembrano, Max Plank Institute, Germany; Jose Correa, Universidad de Chile, Chile; Ulrike Schmidt-Kraepelin, Eindhoven University of Technology, Netherlands; Alexandros Tsigonias-Dimitriadis, European Central Bank, Frankfurt am Main, Germany; Victor Verdugo, Pontificia Universidad Católica de Chile, Chile
| 5:20-5:40 Packing Short Cycles
Matthias Bentert,
Fedor Fomin, and
Petr Golovach, University of Bergen, Norway; Tuukka Korhonen, University of Copenhagen, Denmark; William Lochet, CNRS, France; Fahad Panolan, University of Leeds, United Kingdom; M. S. Ramanujan, University of Warwick, United Kingdom; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Kirill Simonov, Technische Universität Wien, Austria
| 5:20-5:40 Exploring the Landscape of Distributed Graph Sketching
David Tench, Lawrence Berkeley National Laboratory, U.S.; Evan West, Stony Brook University, U.S.; Kenny Zhang, University of Michigan, U.S.; Michael A. Bender and
Daniel Delayo, Stony Brook University, U.S.; Martin Farach-Colton, Rutgers University, U.S.; Gilvir Gill, Stony Brook University, U.S.; Tyler Seip, MongoDB; Victor Zhang, Meta Platforms, Inc., U.S.
|
5:45-6:05 Approximating Traveling Salesman Problems Using a Bridge Lemma
Tobias Mömke, Universität Augsburg, Germany; Martin Böhm, University of Wroclaw, Poland; Zachary Friggstad, University of Alberta, Canada; Joachim Spoerhase, University of Liverpool, United Kingdom
| 5:45-6:05 Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint
Prommy Sultana Hossain, George Mason University, U.S.; Xintong Wang, Rutgers University, U.S.; Fang-Yi Yu, George Mason University, U.S.
| 5:45-6:05 Unbreakable Decomposition in Close-to-Linear Time
Aditya Anand and
Euiwoong Lee, University of Michigan, U.S.; Jason M. Li, Carnegie Mellon University, U.S.; Yaowei Long and
Thatchaphol Saranurak, University of Michigan, U.S.
| 5:45-6:05 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, Germany
|
6:10-6:30 Min-CSPs on Complete Instances
Aditya Anand and
Euiwoong Lee, University of Michigan, U.S.; Amatya Sharma, University of Michigan, Ann Arbor, U.S.
| 6:10-6:30 An Elementary Predictor Obtaining $2\sqrt{T} + 1$ Distance to Calibration
Eshwar Ram Arunachaleswaran,
Natalie Collina,
Aaron Roth, and
Mirah Shi, University of Pennsylvania, U.S.
| 6:10-6:30 The Primal Pathwidth Seth
Michael Lampis, Université Paris Dauphine, France
| |
|
ALENEX Business Meeting
6:15 PM - 7:00 PM |
|
Continental Breakfast
8:30 AM - 9:00 AM |
|
SODA Session 4A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Emily Fox | SODA Session 4B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Kangning Wang | SODA Session 4C
Room: Grand Ballroom A - 2nd Floor
Chair: Bundit Laekhanukit | ALENEX Session 4
Room: St. Charles - 1st Floor
Chair: Christian Schulz |
9:00-9:20 Deterministic Online Bipartite Edge Coloring
Joakim Blikstad, KTH Royal Institute of Technology, Sweden; Ola Svensson, École Polytechnique Fédérale de Lausanne, Switzerland; Radu Vintan, EPFL, Switzerland; David Wajc, Technion Israel Institute of Technology, Israel
| 9:00-9:20 A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
Trung Dang and
Shuchi Chawla, University of Texas at Austin, U.S.; Dimitrios Christou, The University of Texas at Austin, U.S.; Zhiyi Huang, University of Texas at Austin, U.S.; Gregory Kehne and
Rojin Rezvan, The University of Texas at Austin, U.S.
| 9:00-9:20 Linear Equations with Monomial Constraints and Decision Problems in Abelian-by-Cyclic Groups
Ruiwen Dong, Saarland University, Germany
| 9:00-9:20 Constructions, Bounds, and Algorithms for Peaceable Queens
Katie Clinch, University of New South Wales, Australia; Matthew Drescher, University of California, Davis, U.S.; Tony Huynh, Université Libre de Bruxelles, Belgium; Abdallah Saffidine, University of New South Wales, Australia
|
9:25-9:45 Eulerian Graph Sparsification by Effective Resistance Decomposition
Arun Jambulapati, University of Washington, U.S.; Sushant Sachdeva, University of Toronto, Canada; Aaron Sidford, Stanford University, U.S.; Kevin Tian, Microsoft Research, U.S.; Yibin Zhao, University of Toronto, Canada
| 9:25-9:45 Hiring for An Uncertain Task: Joint Design of Information and Contracts
Matteo Castiglioni, Politecnico di Milano, Italy; Junjie Chen, City University of Hong Kong
| 9:25-9:45 An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition
Pascal Koiran, LIP-ENS Lyon, France
| 9:25-9:45 Another L Makes It Better? Lagrange Meets LLL and May Improve BKZ Pre-Processing
Sebastien Balny,
Claire Delaplace, and
Gilles Dequen, Université de Picardie Jules Verne, France
|
9:50-10:10 A Cut-Matching Game for Constant-Hop Expanders
Bernhard Haeupler, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Jonas Huebotter, ETH Zurich, Switzerland; Mohsen Ghaffari, Massachusetts Institute of Technology, U.S.
| 9:50-10:10 A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design
Matteo Castiglioni, Politecnico di Milano, Italy; Junjie Chen, City University of Hong Kong; Minming Li, City University of Hong Kong, Hong Kong; Haifeng Xu, University of Chicago, U.S.; Song Zuo, Google Research, U.S.
| 9:50-10:10 Improving the Leading Constant of Matrix Multiplication
Hantao Yu, Columbia University, U.S.; Josh Alman, Columbia University, U.S.
| 9:50-10:10 HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees
Aniss A. Medbouhi, KTH Royal Institute of Technology, Sweden; Alejandro García-Castellanos, VU University Amsterdam, Netherlands; Giovanni Luca Marchetti and
Danica Kragic, KTH Royal Institute of Technology, Sweden; Erik Johannes Bekkers, University of Amsterdam, Netherlands
|
10:15-10:35 Quasilinear-Time Eccentricities Computation, and More, on Median Graphs
Pierre Bergé, Université Clermont Auvergne, France; Ducoffe Guillaume, University of Bucharest, Romania; Habib Michel, Université Paris Cité, France
| 10:15-10:35 Majorized Bayesian Persuasion and Fair Selection
Siddhartha Banerjee, Cornell University, U.S.; Kamesh Munagala and
Yiheng Shen, Duke University, U.S.; Kangning Wang, Rutgers University, U.S.
| 10:15-10:35 Faster Linear Systems and Matrix Norm Approximation Via Multi-Level Sketched Preconditioning
Michal Derezinski, University of Michigan, U.S.; Christopher Musco, New York University, U.S.; Jiaming Yang, University of Michigan, U.S.
| 10:15-10:35 A Greedy Algorithm for Low-Crossing Partitions for General Set Systems
Monika Csikos and
Alexandre Louvet, ; Nabil Mustafa, Université Sorbonne Paris Nord, France
|
10:40-11:00 Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
Daoyuan Chen and
Simon Meierhans, ETH Zurich, Switzerland; Maximilian Probst Gutenberg, ; Thatchaphol Saranurak, University of Michigan, U.S.
| 10:40-11:00 Multi-Agent Combinatorial Contracts
Paul Duetting, Google Research, U.S.; Tomer Ezra, Harvard University, U.S.; Michal Feldman, Tel Aviv University, Israel; Thomas Kesselheim, Universität Bonn, Germany
| 10:40-11:00 More Asymmetry Yields Faster Matrix Multiplication
Josh Alman, Columbia University, U.S.; Ran Duan, Tsinghua University, P. R. China; Virginia Vassilevska Williams,
Yinzhan Xu, and
Zixuan Xu, Massachusetts Institute of Technology, U.S.; Renfei Zhou, Carnegie Mellon University, U.S.
| 10:40-11:00 Spiderdan: Matching Augmentation in Demand-Aware Networks
Aleksander Figiel,
Darya Melnyk,
André Nichterlein,
Arash Pourdamghani, and
Stefan Schmid, Technische Universität Berlin, Germany
|
| | | |
|
Coffee Break
11:05 AM - 11:30 AM |
|
SODA Best Paper and Best Student Paper Prize Session
Room: Grand Ballroom C/D - 2nd Floor
Chair: Debmalya Panigrahi
11:30-11:50 Improved List Size for Folded Reed-Solomon Codes
Shashank Srivastava, Rutgers University, U.S.
11:55-12:15 Quasi-Monte Carlo Beyond Hardy-Krause
Nikhil Bansal, University of Michigan, U.S.; Haotian Jiang, University of Chicago, U.S.
12:20-12:40 Tight Streaming Lower Bounds for Deterministic Approximate Counting
Yichuan Wang, Tsinghua University, China
|
|
Lunch Break
12:45 PM - 2:00 PM |
|
SODA Session 5A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Sanjeev Khanna | SODA Session 5B
Room: Toulouse - 2nd Floor Mezzanine
Chair: R Ravi | SODA Session 5C
Room: Grand Ballroom A - 2nd Floor
Chair: Emily Fox | SOSA Session 1: Sublinear Algorithms
Room: St. Charles - 1st Floor
Chair: Iona Bercea |
2:00-2:20 A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
Chandra Chekuri and
Rhea Jain, University of Illinois Urbana-Champaign
| 2:00-2:20 Testing Approximate Stationarity Concepts for Piecewise Affine Functions
Lai Tian, The Chinese University of Hong Kong, Hong Kong; Anthony So, Chinese University of Hong Kong, Hong Kong
| 2:00-2:20 Flipping Non-Crossing Spanning Trees
Birgit Vogtenhuber, Graz University of Technology, Austria; Håvard Bjerkevik, University at Albany, U.S.; Linda Kleist, Universität Potsdam, Germany; Torsten Ueckerdt, Karlsruhe Institute of Technology, Germany
| 2:00-2:20 Simple Sublinear Algorithms for (Delta + 1) Vertex Coloring Via Asymmetric Palette Sparsification
Sepehr Assadi and
Helia Yazdanyar, University of Waterloo, Canada
|
2:25-2:45 Congestion-Approximators from the Bottom Up
Jason M. Li, Carnegie Mellon University, U.S.
| 2:25-2:45 Forall-Exist Statements in Pseudopolynomial Time
Eleonore Bach, EPFL, France; Friedrich Eisenbrand, École Polytechnique Fédérale de Lausanne, Switzerland; Thomas Rothvoss, University of Washington, U.S.; Robert Weismantel, ETH Zurich, Switzerland
| 2:25-2:45 Ptases for Euclidean Tsp with Unit Disk and Unit Square Neighborhoods
William Lochet, CNRS, France; Sayan Bandyapadhyay, Portland State University, U.S.; katie clinch, University of New South Wales, Australia; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Saket Saurabh, Institute of Mathematical Sciences, India and University of Bergen, Norway; Jie Xue, New York University-Shanghai, China
| 2:25-2:45 How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
John M. Kallaugher and
Ojas Parekh, Sandia National Laboratories, U.S.; Nadezhda Voronova, Boston University, U.S.
|
2:50-3:10 (Almost) Ruling Out Seth Lower Bounds for All-Pairs Max-Flow
Ohad Trabelsi, Toyota Technological Institute at Chicago, U.S.
| 2:50-3:10 Complexity of Polytope Diameters Via Perfect Matchings
Christian Nöbel and
Raphael Steiner, ETH Zurich, Switzerland
| 2:50-3:10 Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
Sujoy Bhore, Indian Institute of Technology Bombay, India; Timothy M. Chan, University of Illinois Urbana-Champaign
| 2:50-3:10 Sublinear-Time Algorithm for MST-Weight Revisited
Gryphon Patlin and
Jan van den Brand, Georgia Institute of Technology, U.S.
|
3:15-3:35 Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and All Eccentricities in Graphs
Feodor F. Dragan, Kent State University, U.S.; Guillaume Ducoffe, ICI – National Institute for Research and Development informatics, Romania; Michel Habib, Université Paris, France; Laurent Viennot, Inria, France
| 3:15-3:35 The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms
Naren S. Manoj and
Max Ovsiankin, Toyota Technological Institute at Chicago, U.S.
| 3:15-3:35 Strict Self-Assembly of Discrete Self-Similar Fractals in the Abstract Tile Assembly Model
Florent Becker, Universite d'Orleans, France; Daniel Hader and
Matthew Patitz, University of Arkansas, U.S.
| 3:15-3:35 Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Christian J. Lebeda, Inria, France
|
3:40-4:00 Flip Dynamics for Sampling Colorings: Improving $(11/6-\varepsilon)$ Using A Simple Metric
Charlie A. Carlson, University of California, Santa Barbara, U.S.; Eric Vigoda, University of California, Santa Barbara, U.S.
| 3:40-4:00 Integer Programs with Nearly Totally Unimodular Matrices: the Cographic Case
Manuel Aprile, Universita di Padova, Italy; Samuel Fiorini and
Gwenaël Joret, Université Libre de Bruxelles, Belgium; Stefan Kober, Université libre de Bruxelles, Belgium; Michal Seweryn, Charles University, Prague, Czech Republic; Stefan Weltge, Technische Universität München, Germany; Yelena Yuditsky, McGill University, Canada
| 3:40-4:00 Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
Yu Chen, National University of Singapore, Singapore; Zihan Tan, Rutgers University, U.S.
| 3:40-4:00 On Optimal Testing of Linearity
Vipul Arora, National University of Singapore, Singapore; Esty Kelman, Boston University, and Massachusetts Institute of Technology, U.S.; Uri Meir, Tel Aviv University, Israel; Ephraim Linder, Boston University, U.S.
|
| | | |
|
Coffee Break
4:05 PM - 4:30 PM |
|
SODA Session 6A
Room: Grand Ballroom C/D - 2nd Floor
Chair: R Ravi | SODA Session 6B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Karthik CS | SODA Session 6C
Room: Grand Ballroom A - 2nd Floor
Chair: Debmalya Panigrahi | SOSA Session 2: Randomization
Room: St. Charles - 1st Floor
Chair: Cliff Stein |
4:30-4:50 On the Uniqueness of Bayesian Coarse Correlated Equilibria in Standard First-Price and All-Pay Auctions
Mete Seref Ahunbay and
Martin Bichler, Technical University of Munich, Germany
| 4:30-4:50 Near-Optimal Hierarchical Matrix Approximation from Matrix-Vector Products
Feyza Duman Keles and
Tyler Chen, New York University, U.S.; Diana Halikias, Cornell University, U.S.; Cameron Musco, University of Massachusetts, Amherst, U.S.; Christopher Musco, New York University, U.S.; David Persson, École Polytechnique Fédérale de Lausanne, Switzerland
| 4:30-4:50 Private Mean Estimation with Person-Level Differential Privacy
Rose Silver, Carnegie Mellon University, U.S.; Sushant Agarwal, Northeastern University, U.S.; Gautam Kamath, University of Waterloo, Canada; Mahbod Majid, Massachusetts Institute of Technology, U.S.; Argyris Mouzakis, University of Waterloo, Canada; Jonathan Ullman, Northeastern University, U.S.
| 4:30-4:50 A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
William Kuszmaul, Massachusetts Institute of Technology, U.S.
|
4:55-5:15 Approximating Competitive Equilibrium by Nash Welfare
Jugal Garg, University of Illinois Urbana-Champaign; Yixin Tao, Shanghai University of Finance and Economics, China; László Végh, Bonn University, Germany
| 4:55-5:15 Improved Spectral Density Estimation Via Explicit and Implicit Deflation
Rajarshi Bhattacharjee, University of Massachusetts, Amherst, U.S.; Rajesh Jayaram, Google Research, U.S.; Cameron Musco, University of Massachusetts, Amherst, U.S.; Christopher Musco, New York University, U.S.; Archan Ray, Memorial Sloan-Kettering Cancer Center, U.S.
| 4:55-5:15 Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
Jane Lange, Massachusetts Institute of Technology, U.S.; Ephraim Linder and
Sofya Raskhodnikova, Boston University, U.S.; Arsen Vasilyan, Michigan State University, U.S.
| 4:55-5:15 Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size
Kodai Tanaka, Tohoku University, Japan; Shun Sasaki and
Kazumasa Shinagawa, Ibaraki University, Japan; Takaaki Mizuki, Tohoku University, Japan
|
5:20-5:40 Tolls for Dynamic Equilibrium Flows
Julian Schwarz,
Tobias Harks, and
Lukas Graf, University of Passau, Germany
| 5:20-5:40 On the Decidability of Presburger Arithmetic Expanded with Powers
Toghrul Karimov, Max Planck Institute for Software Systems, Germany; Florian Luca, Stellenbosch University, South Africa; Joris Nieuwveld and
Joël Ouaknine, Max Planck Institute for Software Systems, Germany; James Worrell, University of Oxford, United Kingdom
| 5:20-5:40 Almost Tight Bounds for Differentially Private Densest Subgraph
Michael Dinitz, Johns Hopkins University, U.S.; Satyen Kale, Apple, France; Silvio Lattanzi, Google Zurich, Switzerland; Sergei Vassilvitskii, Google Research, U.S.
| 5:20-5:40 A Multilinear Johnson-Lindenstrauss Transform
Antonis Matakos,
Petteri Kaski, and
Heikki Mannila, Aalto University, Finland
|
5:45-6:05 Platforms for Efficient and Incentive-Aware Collaboration
Nika Haghtalab,
Mingda Qiao, and
Kunhe Yang, University of California, Berkeley, U.S.
| 5:45-6:05 Solving Polynomial Equations Over Finite Fields
Holger Dell, IT University of Copenhagen, Denmark; Anselm Haak, Universität Paderborn, Germany; Melvin Kallmayer, Goethe Universität Frankfurt, Germany; Leo Wennmann, Maastricht University, The Netherlands
| 5:45-6:05 Improved Differentially Private Continual Observation Using Group Algebra
Jalaj Upadhyay, Rutgers University, U.S.; Monika Henzinger, Institute of Science and Technology Austria, Austria
| 5:45-6:05 Better Gaussian Mechanism Using Correlated Noise
Christian J. Lebeda, Inria, France
|
6:10-6:30 Clock Auctions Augmented with Unreliable Advice
Vasilis Gkatzelis,
Daniel Schoepflin, and
Xizhi Tan, Drexel University, U.S.
| 6:10-6:30 Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
Andreas Björklund, IT University of Copenhagen, Denmark; Kevin Pratt, New York University, U.S.; Petteri Kaski, Aalto University, Finland; Thore Husfeldt, IT University of Copenhagen, Denmark; Radu Curticapean, University of Regensburg, Germany and IT University of Copenhagen, Denmark
| | 6:10-6:30 Ellipsoid Fitting Up to Constant Via Empirical Covariance Estimation
June Wu, University of Chicago, U.S.; Madhur Tulsiani, Toyota Technological Institute at Chicago, U.S.
|
|
SODA Business Meeting & Awards Presentation, followed by SOSA Business Meeting **Complimentary beer and wine will be served**
6:45 PM - 7:45 PM |
|
Continental Breakfast
8:30 AM - 9:00 AM |
|
SODA Session 7A
Room: Grand Ballroom C/D - 2nd Floor
Chair: William Umboh | SODA Session 7B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Nikhil Bansal | SODA Session 7C
Room: Grand Ballroom A - 2nd Floor
Chair: Artur Czumaj | SOSA Session 3: Data Structures and Preprocessing
Room: St. Charles - 1st Floor
Chair: Robert Tarjan |
9:00-9:20 Improved Bounds for Fully Dynamic Matching Via Ordered Ruzsa-Szemeredi Graphs
Sepehr Assadi, University of Waterloo, Canada; Sanjeev Khanna, University of Pennsylvania, U.S.; Peter Kiss, University of Vienna, Austria
| 9:00-9:20 Bounding $\varepsilon$-Scatter Dimension Via Metric Sparsity
Romain Bourneuf, Inria-LIP-ENS Lyon, France; Marcin Pilipczuk, University of Warsaw, Poland
| 9:00-9:20 An Analogue of Reed's Conjecture for Digraphs
Ken-ichi Kawarabayashi and
Lucas Picasarri-Arrieta, National Institute of Informatics, Japan
| 9:00-9:20 Multi-Dimensional Approximate Counting
Dingyu Wang, University of Michigan, U.S.
|
9:25-9:45 Matching Composition and Efficient Weight Reduction in Dynamic Matching
Aaron Bernstein, Rutgers University, U.S.; Jiale Chen, Stanford University, U.S.; Aditi Dudeja, University of Salzburg, Austria; Zachary Langley, Rutgers University, U.S.; Aaron Sidford and
Ta-Wei Tu, Stanford University, U.S.
| 9:25-9:45 The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction
Erik Waingarten, University of Pennsylvania, U.S.; Moses Charikar, Stanford University, U.S.
| 9:25-9:45 Weak Coloring Numbers of 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, CEPAM - CNRS, France
| 9:25-9:45 3sum in Preprocessed Universes: Faster and Simpler
Adam Polak, Bocconi University, Italy; Shashwat Kasliwal and
Pratyush Sharma, IIT Delhi, India
|
9:50-10:10 Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
Joseph (Seffi) Naor, Technion Israel Institute of Technology, Israel; Aravind Srinivasan, University of Maryland, College Park, U.S.; David Wajc, Technion Israel Institute of Technology, Israel; Tristan Pollner, Stanford University, U.S.
| 9:50-10:10 Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models Via Truncated Metrics
Moses Charikar,
Spencer Compton, and
Chirag Pabbaraju, Stanford University, U.S.
| 9:50-10:10 Unique-Neighbor Expanders with Better Expansion for Polynomial-Sized Sets
Yeyuan Chen, University of Michigan, Ann Arbor, U.S.
| 9:50-10:10 Optimal Prefix-Suffix Queries with Applications
Solon P. Pissis, CWI, Amsterdam, Netherlands
|
10:15-10:35 Entropy Regularization and Faster Decremental Matching in General Graphs
Jiale Chen,
Aaron Sidford, and
Ta-Wei Tu, Stanford University, U.S.
| 10:15-10:35 Highway Dimension: a Metric View
Andreas E. Feldmann, University of Sheffield, United Kingdom; Arnold Filtser, Bar-Ilan University, Israel
| 10:15-10:35 A Coarse Erd\H{o}s-P\'{o}sa Theorem
Jungho Ahn, Korea Institute for Advanced Study, Korea; Jochen Pascal Gollin, University of Primorska, Slovenia; Tony Huynh, Université Libre de Bruxelles, Belgium; O-Joung Kwon, Hanyang University, South Korea
| 10:15-10:35 Pure Binary Finger Search Trees
Gerth S. Brodal and
Casper Rysgaard, Aarhus University, Denmark
|
10:40-11:00 New Philosopher Inequalities for Online Bayesian Matching, Via Pivotal Sampling
Mark Braverman, Princeton University, U.S.; Mahsa Derakhshan, Northeastern University, U.S.; Tristan Pollner and
Amin Saberi, Stanford University, U.S.; David Wajc, Technion Israel Institute of Technology, Israel
| 10:40-11:00 Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
Hongjie Chen, ETH Zurich, Switzerland; Deepak Narayanan Sridharan, ETH Zurich, Switzerland; David Steurer, ETH Zurich, Switzerland
| 10:40-11:00 Planar Graphs in Blowups of Fans
Pat Morin, Carleton University, Canada
| 10:40-11:00 A Simple Algorithm for Dynamic Carpooling with Recourse
Yuval Efron,
Shyamal Patel, and
Cliff Stein, Columbia University, U.S.
|
| | | |
|
Coffee Break
11:05 AM - 11:30 AM |
|
IP2 When and Why do Efficient Algorithms Exist (for Constraint Satisfaction and Beyond)?
Room: Grand Ballroom C/D - 2nd Floor
Chair: SIAM Conference Participation System
11:30 AM - 12:30 PM |
|
Lunch Break
12:30 PM - 2:00 PM |
|
SODA Session 8A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Mike Dinitz | SODA Session 8B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Hung Le | SODA Session 8C
Room: Grand Ballroom A - 2nd Floor
Chair: Venkat Guruswami | SOSA Session 4: Optimization, Parallel and Distributed Algorithms
Room: St. Charles - 1st Floor
Chair: Seth Pettie |
2:00-2:20 Streaming Algorithms Via Local Algorithms for Maximum Directed Cut
Santhoshini Velusamy, Toyota Technological Institute at Chicago, U.S.; Raghuvansh Saxena, Microsoft Research, U.S.; Noah Singer, Carnegie Mellon University, U.S.; Madhu Sudan, Harvard University, U.S.
| 2:00-2:20 A Fast Algorithm for Computing Zigzag Representatives
Tamal K. Dey, Purdue University, U.S.; Tao Hou, University of Oregon, U.S.; Dmitriy Morozov, Lawrence Berkeley National Laboratory, U.S.
| 2:00-2:20 Hardness of Counting Small Induced Subgraphs: Fourier vs. Sylow
Philip Wellnitz and
Simon Döring, Max Planck Institute for Informatics, Germany; Dániel Marx, CISPA Helmholtz Center for Information Security, Germany; Radu Curticapean, University of Regensburg, Germany and IT University of Copenhagen, Denmark; Daniel Neuen, Max Planck Institute for Informatics, Germany
| 2:00-2:20 Bidirectional Dijkstra's Algorithm Is Instance-Optimal
Bernhard Haeupler, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Richard Hladík, Sofia University, Bulgaria; Václav Rozhon, ETH Zurich, Switzerland; Robert Tarjan, Princeton University, U.S.; Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria
|
2:25-2:45 Universal Perfect Samplers for Incremental Streams
Dingyu Wang, University of Michigan, U.S.; Seth Pettie, University of Michigan, Ann Arbor, U.S.
| 2:25-2:45 Minimum Convex Hull and Maximum Overlap of Two Convex Polytopes
Mook Kwon Jung,
Seokyun Kang, and
Hee-Kap Ahn, POSTECH, Korea
| 2:25-2:45 Maximum Span Hypothesis: A Potentially Weaker Assumption Than Gap-ETH for Parameterized Complexity
Karthik C. S., Rutgers University, U.S.; Subhash Khot, New York University, U.S.
| 2:25-2:45 A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Path
Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Bernhard Haeupler, ETH Zurich, Switzerland; Rustam Latypov, Aalto University, Finland; Antti Roeyskoe and
Aurelio L. Sulser, ETH Zurich, Switzerland
|
2:50-3:10 Streaming and Communication Complexity of Load-Balancing Via Matching Contractors
Sepehr Assadi, University of Waterloo, Canada; Aaron Bernstein, Rutgers University, U.S.; Zach Langley, Rutgers University, U.S.; Lap Chi Lau and
Robert Wang, University of Waterloo, Canada
| 2:50-3:10 Partitioning a Polygon Into Small Pieces
Mikkel Abrahamsen,
Nichlas Rasmussen, and
Mads Jensen, University of Copenhagen, Denmark
| 2:50-3:10 Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
Ignasi Sau, CNRS, LIRMM, France; Giannos Stamoulis, University of Warsaw, Poland; Dimitrios Thilikos, CNRS, LIRMM, France
| 2:50-3:10 Efficient Matroid Intersection Via a Batch-Update Auction Algorithm
Joakim Blikstad, KTH Royal Institute of Technology, Sweden; Ta-Wei Tu, Stanford University, U.S.
|
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 University, China
| 3:15-3:35 Computing the Second and Third Systoles of a Combinatorial Surface
Matthijs Ebbens, University of Cologne, Germany; Francis Lazarus, Universite Grenoble, France
| 3:15-3:35 Losing Treewidth In The Presence Of Weights
Michal Wlodarczyk, University of Warsaw, Poland
| 3:15-3:35 Trading Prophets: How to Trade Multiple Stocks Optimally
Surbhi Rajput,
Ashish Chiplunkar, and
Rohit Vaish, Indian Institute of Technology, Delhi, India
|
3:40-4:00 Near-Optimal Relative Error Streaming Quantile Estimation Via Elastic Compactors
Hongxun Wu, University of California, Berkeley, U.S.; Elena Gribelyuk,
Pachara Sawettamalya, and
Huacheng Yu, Princeton University, U.S.
| 3:40-4:00 An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs
Natan Rubin, Ben-Gurion University, Israel
| 3:40-4:00 Finding irrelevant vertices in linear time on bounded-genus graphs
Petr Golovach, University of Bergen, Norway; Stavros Kolliopoulos, National and Kapodistrian University of Athens, Greece; Giannos Stamoulis, University of Warsaw, Poland; Dimitrios Thilikos, CNRS, LIRMM, France
| 3:40-4:00 A Simple Lower Bound for Set Agreement in Dynamic Networks
Pierre Fraigniaud, Universite Paris Sud & CNRS, France; Minh Hang Nguyen, Université Paris Cité, France; Ami Paz, CNRS LISN, Universite Paris-Saclay, France
|
| | | |
|
Coffee Break
4:05 PM - 4:30 PM |
|
SODA Session 9A
Room: Grand Ballroom C/D - 2nd Floor
Chair: William Umboh | SODA Session 9B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Seth Pettie | SODA Session 9C
Room: Grand Ballroom A - 2nd Floor
Chair: Rajmohan Rajaraman | SOSA Session 5: Approximation Algorithms for Graphs
Room: St. Charles - 1st Floor
Chair: Tobias Mömke |
4:30-4:50 Competitive Strategies to Use "Warm Start" Algorithms with Predictions
Avrim Blum, Toyota Technological Institute at Chicago, U.S.; Vaidehi Srinivas, Northwestern University, U.S.
| 4:30-4:50 Efficient $d$-Ary Cuckoo Hashing at High Load Factors by Bubbling Up
William Kuszmaul, Carnegie Mellon University, U.S.; Michael Mitzenmacher, Harvard University, U.S.
| 4:30-4:50 Parks and Recreation: Color Fault-Tolerant Spanners Made Local
Asaf Petruschka,
Merav Parter,
Shay Sapir, and
Elad Tzalik, Weizmann Institute of Science, Israel
| 4:30-4:50 Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
Yijia Chen, Shanghai Jiao Tong University, China; Yi Feng, Shanghai University of Finance and Economics, China; Bundit Laekhanukit, Independent Researcher; Yanlin Liu, Ocean University of China, Qiandao, China
|
4:55-5:15 Online Scheduling Via Gradient Descent for Weighted Flow Time Minimization
Qingyun Chen,
Sungjin Im, and
Aditya Petety, University of California, Merced, U.S.
| 4:55-5:15 Fast and Simple Sorting Using Partial Information
Richard Hladík, Sofia University, Bulgaria; Bernhard Haeupler, ETH Zurich, Switzerland; John Iacono, Université libre de Bruxelles, Belgium; Václav Rozhon, ETH Zurich, Switzerland; Robert Tarjan, Princeton University, U.S.; Jakub Tetek, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria
| 4:55-5:15 Asynchronous 3-Majority Dynamics with Many Opinions
Nobutaka Shimizu, Institute of Science Tokyo, Japan; Colin Cooper,
Frederik Mallmann-Trenn, and
Tomasz Radzik, King's College London, United Kingdom; Takeharu Shiraga, Chuo University, Japan
| 4:55-5:15 Validating a Ptas for Triangle-Free 2-Matching
Yusuke Kobayashi and
Takashi Noguchi, Kyoto University, Japan
|
5:20-5:40 Stronger Adversaries Grow Cheaper Forests: Online Node-Weighted Steiner Problems
Sander Borst, Centrum Wiskunde & Informatica, Netherlands; Marek Elias and
Moritz Venzin, Bocconi University, Italy
| 5:20-5:40 Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
Aaron L. Putterman, Harvard University, U.S.; William Kuszmaul, Carnegie Mellon University, U.S.; Tingqiang Xu and
Hangrui Zhou, Tsinghua University, P. R. China; Renfei Zhou, Carnegie Mellon University, U.S.
| 5:20-5:40 Sublinear-Round Broadcast Without Trusted Setup
Andreea Alexandru, Duality Technologies, U.S.; Julian Loss, CISPA Helmholtz Center for Information Security, Germany; Charalampos Papamanthou, Yale University, U.S.; Giorgos Tsimos, University of Maryland, U.S.; Benedikt Wagner, Ethereum Foundation, Switzerland
| 5:20-5:40 Simple Approximation Algorithms for Polyamorous Scheduling
Yuriy Biktairov, University of Southern California, U.S.; Leszek Gasieniec, University of Liverpool, United Kingdom; Wanchote Po Jiamjitrak, University of Helsinki, Finland; N Namrata and
Benjamin Smith, University of Liverpool, United Kingdom; Sebastian Wild, University of Marburg, Germany
|
5:45-6:05 Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
Benjamin Moseley,
Aidin Niaparast, and
R. Ravi, Carnegie Mellon University, U.S.
| 5:45-6:05 A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM
Peyman Afshani, Aarhus University, Denmark; Nodari Sitchinava, University of Hawaii at Manoa, U.S.
| 5:45-6:05 Fully-Distributed Byzantine Agreement in Sparse Networks
John Augustine, IIT Mumbai, India; Fabien Dufoulon, Lancaster University, United Kingdom ; Gopal Pandurangan, University of Houston, U.S.
| 5:45-6:05 Spectral Sparsification by Deterministic Discrepancy Walk
Lap Chi Lau and
Robert Wang, University of Waterloo, Canada; Hong Zhou, Fuzhou University, China
|
6:10-6:30 Unweighted Layered Graph Traversal: Passing a Crown Via Entropy Maximization
Romain Cosson, Inria, France; Xingjian Bai, Massachusetts Institute of Technology, U.S.; Christian Coester, University of Oxford, United Kingdom
| 6:10-6:30 Top-K Document Retrieval in Compressed Space
Gonzalo Navarro, University of Chile, Chile; Yakov Nekrich, Michigan Technological University, U.S.
| 6:10-6:30 On the Locality of Hall's Theorem
Sebastian Brandt, CISPA Helmholtz Center for Information Security, Germany; Yannic Maus, Technische Universität, Graz, Austria; Ananth Narayanan, CISPA Helmholtz Center for Information Security, Germany; Florian Schager, TU Graz; Jara Uitto, Aalto University, Finland
| 6:10-6:30 Simple Length-Constrained Minimum Spanning Trees
Ellis Hershkowitz and
Richard Huang, Brown University, U.S.
|
6:35-6:55 The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints
Sven Jäger, RPTU Kaiserslautern-Landau, Germany; Alexander Lindermayr and
Nicole Megow, Universität Bremen, Germany
| 6:35-6:55 Faster Two-Dimensional Pattern Matching with $k$ Mismatches
Jonas Ellert, ENS Paris Saclay, France; Pawel Gawrychowski and
Adam Gorkiewicz, University of Wroclaw, Poland; Tatiana Starikovskaya, École Normale Supérieure Paris, France
| 6:35-6:55 Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement
Pierre Civit, EPFL, Switzerland; Ayaz Dzulfikar and
Seth Gilbert, National University of Singapore, Singapore; Rachid Guerraoui,
Jovan Komatovic, and
Manuel Vidigueira, EPFL, Switzerland; Igor Zablotchi, Mysten Labs, Greece
| |
|
https://www.siam.org/conferences-events/siam-
conferences/soda25/program/special-events/
7:00 PM - 8:00 PM |
|
Continental Breakfast
8:30 AM - 9:00 AM |
|
SODA Session 10A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Nikhil Bansal | SODA Session 10B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Venkat Guruswami | SODA Session 10C
Room: Grand Ballroom A - 2nd Floor
Chair: Avrim Blum | SOSA Session 6: Graphs
Room: St. Charles - 1st Floor
Chair: Sepehr Assadi |
9:00-9:20 Spanners in Planar Domains Via Steiner Spanners and Non-Steiner Tree Covers
Hung Le, University of Massachusetts, Amherst, U.S.; Sujoy Bhore, IIT Bombay, India; Balázs Keszegh, Renyi Institute, Hungary ; Andrey Kupavskii, CNRS - Ecole Normale Superieure, France; Alexandre Louvet, ; Dömötör Pálvölgyi, MTA-ELTE, Budapest; Csaba D. Toth, California State University, Northridge, U.S.
| 9:00-9:20 New Separations and Reductions for Directed Hopsets and Preservers
Yinzhan Xu, Massachusetts Institute of Technology, U.S.; Gary Hoppenworth, University of Michigan, U.S.; Zixuan Xu, Massachusetts Institute of Technology, U.S.
| 9:00-9:20 Sumsets, 3SUM, Subset Sum: Now for Real!
Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria
| 9:00-9:20 Simpler Optimal Sorting from a Directed Acyclic Graph
Ivor Van Der Hoog,
Eva Rotenberg, and
Daniel P. Rutschmann, Technical University of Denmark, Denmark
|
9:25-9:45 A Lower Bound for Light Spanners in General Graphs
Greg Bodwin and
Jeremy Flics, University of Michigan, U.S.
| 9:25-9:45 Tree Independence Number IV. Even-Hole-Free Graphs
Maria Chudnovsky, Princeton University, U.S.; Peter Gartland, University of California, Santa Barbara, U.S.; Sepehr Hajebi, University of Waterloo, Canada; Daniel Lokshtanov, University of California, Santa Barbara, U.S.; Sophie Spirkl, University of Waterloo, Canada
| 9:25-9:45 New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Ce Jin and
Yinzhan Xu, Massachusetts Institute of Technology, U.S.
| 9:25-9:45 Finding Longer Cycles Via Shortest Colourful Cycle
Andreas Björklund and
Thore Husfeldt, IT University of Copenhagen, Denmark
|
9:50-10:10 Subquadratic Algorithms in Minor-Free Digraphs: (weighted) Distance Oracles, Decremental Reachability, and More
Adam Karczmarz, University of Warsaw, Poland; Da Wei Zheng, University of Illinois Urbana-Champaign
| 9:50-10:10 A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
Seth Pettie, University of Michigan, Ann Arbor, U.S.; Gábor Tardos, Renyi Institute, Hungary
| 9:50-10:10 Beating Bellman's Algorithm for Subset Sum
Karl Bringmann, Saarland University and Max Planck Institute for Informatics, Germany; Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Vasileios Nakos, National & Kapodistrian University of Athens, Greece
| 9:50-10:10 Connectivity Certificate Against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
Elad Tzalik and
Merav Parter, Weizmann Institute of Science, Israel
|
10:15-10:35 Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets
Shimon Kogan and
Merav Parter, Weizmann Institute of Science, Israel
| 10:15-10:35 Recognizing Sumsets is NP-Complete
Amir Abboud, Weizmann Institute of Science, Israel; Nick Fischer, INSAIT, Sofia University “St. Kliment Ohridski", Bulgaria; Ron Safier and
Nathan Wallheimer, Weizmann Institute of Science, Israel
| 10:15-10:35 Average-Case Hardness of Parity Problems: Orthogonal Vectors, K-Sum and More
Mina Dalirrooyfard, Morgan Stanley, U.S.; Andrea Lincoln, Boston University, U.S.; Barna Saha, University of California, San Diego, U.S.; Virginia Vassilevska Williams, Massachusetts Institute of Technology, U.S.
| 10:15-10:35 A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
Ziliang Xiong and
Mingyu Xiao, University of Electronic Science and Technology of China, China
|
10:40-11:00 Improved Online Reachability Preservers
Greg Bodwin and
Tuong Le, University of Michigan, U.S.
| 10:40-11:00 A Topological Proof Of The Hell–Nešetril Dichotomy
Sebastian Meyer, TU Dresden, Germany; Jakub Opršal, University of Birmingham, United Kingdom
| 10:40-11:00 Exact Thresholds for Noisy Non-Adaptive Group Testing
Junren Chen, The University of Hong Kong, Hong Kong; Jonathan Scarlett, National University of Singapore, Singapore
| 10:40-11:00 Connectivity Carcass of a Vertex Subset in a Graph - Both Odd and Even Case
Surender Baswana and
Abhyuday Pandey, Indian Institute of Technology, Kanpur, India
|
| | | |
|
Coffee Break
11:05 AM - 11:30 AM |
|
IP3 Learning in Environments with Carryover Effects
Room: Grand Ballroom C/D - 2nd Floor
Chair: SIAM Conference Participation System
11:30 AM - 12:30 PM |
|
Lunch Break
12:30 PM - 2:00 PM |
|
SODA Session 11A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Rajmohan Rajaraman | SODA Session 11B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Soheil Behnezad | SODA Session 11C
Room: Grand Ballroom A - 2nd Floor
Chair: Hung Le | SOSA Session 7: Algebraic Techniques
Room: St. Charles - 1st Floor
Chair: Thore Husfeldt |
2:00-2:20 Inapproximability of Maximum Diameter Clustering for Few Clusters
Ashwin Padaki, University of Pennsylvania, U.S.; Henry Fleischmann, Carnegie Mellon University, U.S.; Kyrylo Karlov, Charles University, Czech Republic; Karthik C. S., Rutgers University, U.S.; Stepan ZHARKOV, Columbia University, U.S.
| 2:00-2:20 Faster Vizing and Near-Vizing Edge Coloring Algorithms
Sepehr Assadi, University of Waterloo, Canada
| 2:00-2:20 Relating Interleaving and Fréchet Distances Via Ordered Merge Trees
Thijs Beurskens, TU Eindhoven, The Netherlands; Tim Ophelders, TU Eindhoven and Utrecht University, The Netherlands; Bettina Speckmann and
Kevin Verbeek, Technische Universiteit Eindhoven, The Netherlands
| 2:00-2:20 The Quasi-Probability Method and Applications for Trace Reconstruction
Ittai Rubinstein, Massachusetts Institute of Technology, U.S.
|
2:25-2:45 Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
Lingxiao Huang, Nanjing University, China; Jian Li, Tsinghua University, P. R. China; Pinyan Lu, Shanghai University of Finance and Economics, China; Xuan Wu, Nanyang Technological University, Singapore
| 2:25-2:45 A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs
Thomas P. Hayes, University at Buffalo, U.S.; Varsha Dani, Rochester Institute of Technology, U.S.
| 2:25-2:45 Facet-Hamiltonicity
Hugo A. Akitaya, University of Massachusetts, Lowell, U.S.; Jean Cardinal, Université Libre de Bruxelles, Belgium; Stefan Felsner, Technische Universität, Berlin, Germany ; Linda Kleist, Universität Potsdam, Germany; Robert Lauff, Technische Universität Berlin, Germany
| 2:25-2:45 A Parametric Version of the Hilbert Nullstellensatz
Klara Nosan, Université Paris Cité, France; Rida Ait El Manssour, Oxford University, United Kingdom; Nikhil Balaji, Indian Institute of Technology, Delhi, India; Mahsa Shirmohammadi, Université Paris Cité, France; James Worrell, University of Oxford, United Kingdom
|
2:50-3:10 A Tight Vc-Dimension Analysis of Clustering Coresets with Applications
Chris Schwiegelshohn, Aarhus University, Denmark; Vincent Cohen-Addad, Google Research, U.S.; Andrew Draganov, Aarhus University, Denmark; Matteo Russo, Università La Sapienza, Rome, Italy; David Saulpic, IST, Austria
| 2:50-3:10 Even Faster (Delta + 1)-Edge Coloring Via Shorter Multi-Step Vizing Chains
Martin Costa and
Sayan Bhattacharya, University of Warwick, United Kingdom; Shay Solomon, Tel Aviv University, Israel; Tianyi Zhang, ETH Zurich, Switzerland
| 2:50-3:10 Differentiable Approximations for Distance Queries
Ahmed Abdelkader, Google, Inc., U.S.; David M. Mount, University of Maryland, U.S.
| 2:50-3:10 Experimental Design Using Interlacing Polynomials
Lap Chi Lau and
Robert Wang, University of Waterloo, Canada; Hong Zhou, Fuzhou University, China
|
3:15-3:35 Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric
Pankaj K. Agarwal, Duke University, U.S.; Sharath Raghvendra, North Carolina State University, U.S.; Pouyan Shirzadian, Virginia Tech, U.S.; Keegan Yao, Duke University, U.S.
| 3:15-3:35 Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
Aditi Dudeja, University of Salzburg, Austria; Rashmika Goswami and
Michael Saks, Rutgers University, U.S.
| 3:15-3:35 Fr\'echet Distance in Subquadratic Time
Siu-Wing Cheng, Hong Kong University of Science and Technology, Hong Kong; Haoqiang Huang, Hong Kong University of Science and Technology, Hong Kong
| 3:15-3:35 Revisiting Tree Canonization using polynomials
V. Arvind, Chennai Mathematical Institute, India; Samir Datta, Chennai Mathematical Institute and UMI ReLaX, Chennai, India; SALMAN Faris, BITS Pilani, India; Asif Khan, Chennai Mathematical Institute and UMI ReLaX, Chennai, India
|
3:40-4:00 Gains-from-Trade in Bilateral Trade with a Broker
Suho Shin, University of Maryland, U.S.; Ilya Hajiaghayi, Takoma Park Middle School; MohammadTaghi Hajiaghayi and
Gary Peng, University of Maryland, U.S.
| 3:40-4:00 Fully Dynamic $(\Delta+1)$ Coloring Against Adaptive Adversaries
Omer Wasim,
Soheil Behnezhad, and
Rajmohan Rajaraman, Northeastern University, U.S.
| 3:40-4:00 A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces
Loïc Dubois, CNRS / LIGM Université Gustave Eiffel, France; Éric Colin de Verdière, Université Paris-Est, LIGM, CNRS, ENPC, ESIEE Paris, UPEM, Marne-la-Vallée, France; Vincent Despré, Université Henri Poincaré, Loria, France
| 3:40-4:00 Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
Josh Alman,
Alexandr Andoni, and
Hengjie Zhang, Columbia University, U.S.
|
| | | |
|
Coffee Break
4:05 PM - 4:30 PM |
|
SODA Session 12A
Room: Grand Ballroom C/D - 2nd Floor
Chair: Mike Dinitz | SODA Session 12B
Room: Toulouse - 2nd Floor Mezzanine
Chair: Bill Kuszmaul | SODA Session 12C
Room: Grand Ballroom A - 2nd Floor
Chair: Yossi Azar | SOSA Session 8: Geometry in Low and High Dimensions
Room: St. Charles - 1st Floor
Chair: Hugo A. Akitaya |
4:30-4:50 Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
Christopher Ye, University of California, San Diego, U.S.; Barna Saha, University of California, San Diego, U.S.; Virginia Vassilevska Williams and
Yinzhan Xu, Massachusetts Institute of Technology, U.S.
| 4:30-4:50 R\'enyi-Infinity Constrained Sampling with $D^3$ Membership Queries
Yunbum Kook, Georgia Institute of Technology, U.S.; Matthew Zhang, University of Toronto, Canada
| 4:30-4:50 Low Degree Local Correction Over the Boolean Cube
Prashanth Amireddy, Harvard University, U.S.; Amik Raj Behera,
Manaswi Paraashar, and
Srikanth Srinivasan, University of Copenhagen, Denmark; Madhu Sudan, Harvard University, U.S.
| 4:30-4:50 Dynamic Independent Set of Disks (and Hypercubes) Made Easier
Sujoy Bhore, Indian Institute of Technology Bombay, India; Timothy M. Chan, University of Illinois Urbana-Champaign
|
4:55-5:15 All-Hops Shortest Paths
Yinzhan Xu,
Virginia Vassilevska Williams, and
Zoe Xi, Massachusetts Institute of Technology, U.S.; Uri Zwick, Tel Aviv University, Israel
| 4:55-5:15 Potential Hessian Ascent: The Sherrington-Kirkpatrick Model
Juspreet Singh Sandhu, University of California, Santa Cruz, U.S.; David Jekel, University of Copenhagen, Denmark; Jonathan Shi, University of California, San Diego, U.S.
| 4:55-5:15 Quantum Locally Recoverable Codes
Louis Golowich and
Venkatesan Guruswami, University of California, Berkeley, U.S.
| 4:55-5:15 A Simple Partially Embedded Planarity Test Based on Vertex-Addition
Simon D. Fink, Technische Universität Wien, Austria; Ignaz Rutter, University of Passau, Germany; Sandhya T P, Stockholms Universitet, Sweden
|
5:20-5:40 New Approximation Algorithms and Reductions for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles
Shiri Chechik,
Itay Hoch, and
Gur Lifshitz, Tel Aviv University, Israel
| 5:20-5:40 Spectral Independence Beyond Total Influence on Trees and Related Graphs
Xiaoyu Chen, Nanjing University, China; Xiongxin Yang, Northeast Normal University, People's Republic of China; Yitong Yin and
Xinyuan Zhang, Nanjing University, China
| 5:20-5:40 Locally Testable Tree Codes
Tamer Mour and
Alon Rosen, Bocconi University, Italy; Ron Rothblum, Technion Israel Institute of Technology, Israel
| 5:20-5:40 An Optimal Algorithm for Half-Plane Hitting Set
Gang Liu and
Haitao Wang, University of Utah, U.S.
|
5:45-6:05 Faster Single-Source Shortest Paths with Negative Real Weights Via Proper Hop Distance
Yufan Huang,
Peter Jin, and
Kent Quanrud, Purdue University, U.S.
| 5:45-6:05 Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie A. Carlson, University of California, Santa Barbara, U.S.; Xiaoyu Chen, Nanjing University, China; Weiming Feng, ETH Zurich, Switzerland; Eric Vigoda, University of California, Santa Barbara, U.S.
| 5:45-6:05 Improved Explicit Near-Optimal Codes in the High-Noise Regimes
Xin Li and
Songtao Mao, Johns Hopkins University, U.S.
| 5:45-6:05 On Beating $2^n$ for the Closest Vector Problem
Rajendra Kumar, Indian Institute of Technology, Delhi, India; Amir Abboud, Weizmann Institute of Science, Israel and INSAIT, Sofia University, Bulgaria
|
6:10-6:30 Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-Offs Between Fault-Tolerance and Subpaths
Greg Bodwin and
Lily Wang, University of Michigan, U.S.
| 6:10-6:30 Mean-Field Potts and Random-Cluster Dynamics from High-Entropy Initializations
Antonio Blanca, Pennsylvania State University, U.S.; Reza Gheissari, Northwestern University, U.S.; Xusheng Zhang, Pennsylvania State University, U.S.
| 6:10-6:30 More Efficient Approximate $k$-Wise Independent Permutations from Random Reversible Circuits Via Log-Sobolev Inequalities
William He, Carnegie Mellon University, U.S.; Lucas Gretta and
Angelos Pelecanos, University of California, Berkeley, U.S.
| 6:10-6:30 Recursive Lattice Reduction-A Framework for Finding Short Lattice Vectors
Divesh Aggarwal, National University of Singapore, Singapore; Thomas Espitau, PQShield; Spencer Peters, Cornell University, U.S.; Noah Stephens-Davidowitz, New York University, U.S.
|
6:35-6:55 Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Vikrant Ashvinkumar, Rutgers University, U.S.; Aaron Bernstein, Rutgers University, U.S.; Adam Karczmarz, University of Warsaw, Poland
| 6:35-6:55 FPTAS for Holant Problems with Log-Concave Signatures
Kun He, Chinese Academy of Sciences, China; Zhidan Li,
Guoliang Qiu, and
Chihao Zhang, Shanghai Jiao Tong University, China
| 6:35-6:55 Hermitian Diagonalization in Linear Precision
Rikhav Shah, University of California, Berkeley, U.S.
| |
|