SODA'25 Day 4 (Wednesday)

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 10A Grand Ballroom C/D - 2nd Floor Chair: Nikhil Bansal (UMich)	SODA 10B Toulouse - 2nd Floor Mezzanine Chair: Venkat Guruswami (UC Berkeley)	SODA 10C Grand Ballroom A - 2nd Floor Chair: Hung Le (UMass Amherst)	SOSA 6 St. Charles - 1st Floor Chair: Sepehr Assadi (Univ. of Waterloo)
9:00-9:20	Spanners in Planar Domains Via Steiner Spanners and Non-Steiner Tree Covers Hung Le (UMass Amherst); Sujoy Bhore (IIT Bombay); Balázs Keszegh (Renyi Institute); Andrey Kupavskii (CNRS - Ecole Normale Superieure); Alexandre Louvet; Dömötör Pálvölgyi (MTA-ELTE); Csaba D. Toth (California State Univ., Northridge)	New Separations and Reductions for Directed Hopsets and Preservers Yinzhan Xu (MIT); Gary Hoppenworth (UMich); Zixuan Xu (MIT)	Sumsets, 3SUM, Subset Sum: Now for Real! Nick Fischer (INSAIT, Sofia Univ.)	Simpler Optimal Sorting from a Directed Acyclic Graph Ivor Van Der Hoog, Eva Rotenberg, and Daniel P. Rutschmann (Technical Univ. of Denmark)
9:25-9:45	A Lower Bound for Light Spanners in General Graphs Greg Bodwin and Jeremy Flics (UMich)	Tree Independence Number IV. Even-Hole-Free Graphs Maria Chudnovsky (Princeton Univ.); Peter Gartland (UC Santa Barbara); Sepehr Hajebi (Univ. of Waterloo); Daniel Lokshtanov (UC Santa Barbara); Sophie Spirkl (Univ. of Waterloo)	New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching Nick Fischer (INSAIT, Sofia Univ.); Ce Jin and Yinzhan Xu (MIT)	Finding Longer Cycles Via Shortest Colourful Cycle Andreas Björklund and Thore Husfeldt (IT Univ. of Copenhagen)
9:50-10:10	Subquadratic Algorithms in Minor-Free Digraphs: (weighted) Distance Oracles, Decremental Reachability, and More Adam Karczmarz (Univ. of Warsaw); Da Wei Zheng (UIUC)	A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices Seth Pettie (UMich); Gábor Tardos (Renyi Institute)	Beating Bellman's Algorithm for Subset Sum Karl Bringmann (Saarland Univ. and Max Planck Institute for Informatics); Nick Fischer (INSAIT, Sofia Univ.); Vasileios Nakos (National & Kapodistrian Univ. of Athens)	Connectivity Certificate Against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults Elad Tzalik and Merav Parter (Weizmann Institute of Science)
10:15-10:35	Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets Shimon Kogan and Merav Parter (Weizmann Institute of Science)	Recognizing Sumsets is NP-Complete Amir Abboud (Weizmann Institute of Science); Nick Fischer (INSAIT, Sofia Univ.); Ron Safier and Nathan Wallheimer (Weizmann Institute of Science)	Average-Case Hardness of Parity Problems: Orthogonal Vectors, K-Sum and More Mina Dalirrooyfard (Morgan Stanley); Andrea Lincoln (Boston Univ.); Barna Saha (UC San Diego); Virginia Vassilevska Williams (MIT)	A Simplified Parameterized Algorithm for Directed Feedback Vertex Set Ziliang Xiong (Linköping Univ.); Mingyu Xiao (Univ. of Electronic Science and Technology of China)
10:40-11:00	Improved Online Reachability Preservers Greg Bodwin and Tuong Le (UMich)	A Topological Proof Of The Hell–Nešetril Dichotomy Sebastian Meyer (TU Dresden); Jakub Opršal (Univ. of Birmingham)	Exact Thresholds for Noisy Non-Adaptive Group Testing Junren Chen (Univ. of Hong Kong); Jonathan Scarlett (National Univ. of Singapore)	Connectivity Carcass of a Vertex Subset in a Graph - Both Odd and Even Case Surender Baswana and Abhyuday Pandey (IIT Kanpur)

11:05 AM - 11:30 AM	Coffee Break	Grand Gallery - 2nd Floor
11:30 AM - 12:30 PM	IP3 Learning in Environments with Carryover Effects Éva Tardos (Cornell Univ.)	Grand Ballroom C/D - 2nd Floor
12:30 PM - 2:00 PM	Lunch Break	Attendees on their own

Time	SODA 11A Grand Ballroom C/D - 2nd Floor Chair: Rajmohan Rajaraman (Northeastern Univ.)	SODA 11B Toulouse - 2nd Floor Mezzanine Chair: Soheil Behnezad (Northeastern Univ.)	SODA 11C Grand Ballroom A - 2nd Floor Chair: Hung Le (UMass Amherst)	SOSA 8 St. Charles - 1st Floor Chair: Hugo A. Akitaya (UMass Lowell)
2:00-2:20	Inapproximability of Maximum Diameter Clustering for Few Clusters Ashwin Padaki (UPenn); Henry Fleischmann (CMU); Kyrylo Karlov (Charles Univ.); Karthik C. S. (Rutgers Univ.); Stepan ZHARKOV (Columbia Univ.)	Faster Vizing and Near-Vizing Edge Coloring Algorithms Sepehr Assadi (Univ. of Waterloo)	Relating Interleaving and Fréchet Distances Via Ordered Merge Trees Thijs Beurskens (TU Eindhoven); Tim Ophelders (TU Eindhoven and Utrecht Univ.); Bettina Speckmann and Kevin Verbeek (TU Eindhoven)	Dynamic Independent Set of Disks (and Hypercubes) Made Easier Sujoy Bhore (IIT Bombay); Timothy M. Chan (UIUC)
2:25-2:45	Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds Lingxiao Huang (Nanjing Univ.); Jian Li (Tsinghua Univ.); Pinyan Lu (Shanghai Univ. of Finance and Economics); Xuan Wu (Nanyang Technological Univ.)	A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs Thomas P. Hayes (Univ. at Buffalo); Varsha Dani (Rochester Institute of Technology)	Facet-Hamiltonicity Hugo A. Akitaya (UMass Lowell); Jean Cardinal (Univ. Libre de Bruxelles); Stefan Felsner (TU Berlin); Linda Kleist (Univ. of Potsdam); Robert Lauff (TU Berlin)	A Simple Partially Embedded Planarity Test Based on Vertex-Addition Simon D. Fink (TU Wien); Ignaz Rutter (Univ. of Passau); Sandhya T P (Stockholms Univ.)
2:50-3:10	A Tight Vc-Dimension Analysis of Clustering Coresets with Applications Chris Schwiegelshohn (Aarhus Univ.); Vincent Cohen-Addad (Google Research); Andrew Draganov (Aarhus Univ.); Matteo Russo (Univ. La Sapienza); David Saulpic (IST)	Even Faster (Delta + 1)-Edge Coloring Via Shorter Multi-Step Vizing Chains Martin Costa and Sayan Bhattacharya (Univ. of Warwick); Shay Solomon (Tel Aviv Univ.); Tianyi Zhang (ETH Zurich)	Differentiable Approximations for Distance Queries Ahmed Abdelkader (Google); David M. Mount (Univ. of Maryland)	An Optimal Algorithm for Half-Plane Hitting Set Gang Liu and Haitao Wang (Univ. of Utah)
3:15-3:35	Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric Pankaj K. Agarwal (Duke Univ.); Sharath Raghvendra (North Carolina State Univ.); Pouyan Shirzadian (Virginia Tech); Keegan Yao (Duke Univ.)	Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs Aditi Dudeja (Univ. of Salzburg); Rashmika Goswami and Michael Saks (Rutgers Univ.)	Fréchet Distance in Subquadratic Time Siu-Wing Cheng (Hong Kong Univ. of Science and Technology); Haoqiang Huang (Hong Kong Univ. of Science and Technology)	$2^n$ for the Closest Vector Problem Rajendra Kumar (IIT Delhi); Amir Abboud (Weizmann Institute of Science and INSAIT, Sofia Univ.)
3:40-4:00	Gains-from-Trade in Bilateral Trade with a Broker Suho Shin (Univ. of Maryland); Ilya Hajiaghayi (Takoma Park Middle School); MohammadTaghi Hajiaghayi and Gary Peng (Univ. of Maryland)	$(\Delta+1)$ Coloring Against Adaptive Adversaries Omer Wasim, Soheil Behnezhad, and Rajmohan Rajaraman (Northeastern Univ.)	A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces Loïc Dubois (CNRS / LIGM Univ. Gustave Eiffel); Éric Colin de Verdière (Univ. Paris-Est); Vincent Despré (Univ. Henri Poincaré)	Recursive Lattice Reduction-A Framework for Finding Short Lattice Vectors Divesh Aggarwal (National Univ. of Singapore); Thomas Espitau (PQShield); Spencer Peters (Cornell Univ.); Noah Stephens-Davidowitz (NYU)

4:05 PM - 4:30 PM	Coffee Break	Grand Gallery - 2nd Floor

Time	SODA 12A Grand Ballroom C/D - 2nd Floor Chair: Mike Dinitz (Johns Hopkins Univ.)	SODA 12B Toulouse - 2nd Floor Mezzanine Chair: Bill Kuszmaul (CMU)	SODA 12C Grand Ballroom A - 2nd Floor Chair: Yossi Azar (Tel Aviv Univ.)	SOSA 8 St. Charles - 1st Floor Chair: Hugo A. Akitaya (UMass Lowell)
4:30-4:50	Fine-Grained Optimality of Partially Dynamic Shortest Paths and More Christopher Ye (UC San Diego); Barna Saha (UC San Diego); Virginia Vassilevska Williams and Yinzhan Xu (MIT)	$D^3$ Membership Queries Yunbum Kook (Georgia Tech); Matthew Zhang (Univ. of Toronto)	Low Degree Local Correction Over the Boolean Cube Prashanth Amireddy (Harvard Univ.); Amik Raj Behera, Manaswi Paraashar, and Srikanth Srinivasan (Univ. of Copenhagen); Madhu Sudan (Harvard Univ.)	Dynamic Independent Set of Disks (and Hypercubes) Made Easier Sujoy Bhore (IIT Bombay); Timothy M. Chan (UIUC)
4:55-5:15	All-Hops Shortest Paths Yinzhan Xu, Virginia Vassilevska Williams, and Zoe Xi (MIT); Uri Zwick (Tel Aviv Univ.)	Potential Hessian Ascent: The Sherrington-Kirkpatrick Model Juspreet Singh Sandhu (UC Santa Cruz); David Jekel (Univ. of Copenhagen); Jonathan Shi (UC San Diego)	Quantum Locally Recoverable Codes Louis Golowich and Venkatesan Guruswami (UC Berkeley)	A Simple Partially Embedded Planarity Test Based on Vertex-Addition Simon D. Fink (TU Wien); Ignaz Rutter (Univ. of Passau); Sandhya T P (Stockholms Univ.)
5:20-5:40	$n$ -Pairs Shortest Paths and All-Nodes Shortest Cycles Shiri Chechik, Itay Hoch, and Gur Lifshitz (Tel Aviv Univ.)	Spectral Independence Beyond Total Influence on Trees and Related Graphs Xiaoyu Chen (Nanjing Univ.); Xiongxin Yang (Northeast Normal Univ.); Yitong Yin and Xinyuan Zhang (Nanjing Univ.)	Locally Testable Tree Codes Tamer Mour and Alon Rosen (Bocconi Univ.); Ron Rothblum (Technion Israel Institute of Technology)	An Optimal Algorithm for Half-Plane Hitting Set Gang Liu and Haitao Wang (Univ. of Utah)
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 Univ.)	Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree Charlie A. Carlson (UC Santa Barbara); Xiaoyu Chen (Nanjing Univ.); Weiming Feng (ETH Zurich); Eric Vigoda (UC Santa Barbara)	Improved Explicit Near-Optimal Codes in the High-Noise Regimes Xin Li and Songtao Mao (Johns Hopkins Univ.)	$2^n$ for the Closest Vector Problem Rajendra Kumar (IIT Delhi); Amir Abboud (Weizmann Institute of Science and INSAIT, Sofia Univ.)
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 (UMich)	Mean-Field Potts and Random-Cluster Dynamics from High-Entropy Initializations Antonio Blanca (Penn State); Reza Gheissari (Northwestern Univ.); Xusheng Zhang (Penn State)	$k$ -Wise Independent Permutations from Random Reversible Circuits Via Log-Sobolev Inequalities William He (CMU); Lucas Gretta and Angelos Pelecanos (UC Berkeley)	Recursive Lattice Reduction-A Framework for Finding Short Lattice Vectors Divesh Aggarwal (National Univ. of Singapore); Thomas Espitau (PQShield); Spencer Peters (Cornell Univ.); Noah Stephens-Davidowitz (NYU)
6:35-6:55	Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs Vikrant Ashvinkumar (Rutgers Univ.); Aaron Bernstein (Rutgers Univ.); Adam Karczmarz (Univ. of Warsaw)	FPTAS for Holant Problems with Log-Concave Signatures Kun He (Chinese Academy of Sciences); Zhidan Li, Guoliang Qiu, and Chihao Zhang (Shanghai Jiao Tong Univ.)	Hermitian Diagonalization in Linear Precision Rikhav Shah (UC Berkeley)