| 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 4A Grand Ballroom C/D - 2nd Floor Chair: Emily Fox (Univ. of Texas at Dallas) | SODA 4B Toulouse - 2nd Floor Mezzanine Chair: Kangning Wang (Stanford Univ.) | SODA 4C Grand Ballroom A - 2nd Floor Chair: Bundit Laekhanukit (Independent Researcher) | ALENEX4 St. Charles - 1st Floor Chair: Christian Schulz (Heidelberg Univ.) |
|---|---|---|---|---|
| 9:00-9:20 | Deterministic Online Bipartite Edge Coloring Joakim Blikstad (KTH Royal Institute of Technology); Ola Svensson (École Polytechnique Fédérale de Lausanne); Radu Vintan (EPFL); David Wajc (Technion Israel Institute of Technology) | A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization Trung Dang and Shuchi Chawla (Univ. of Texas at Austin); Dimitrios Christou (Univ. of Texas at Austin); Zhiyi Huang (Univ. of Texas at Austin); Gregory Kehne and Rojin Rezvan (Univ. of Texas at Austin) | Linear Equations with Monomial Constraints and Decision Problems in Abelian-by-Cyclic Groups Ruiwen Dong (Saarland Univ.) | Constructions, Bounds, and Algorithms for Peaceable Queens Katie Clinch (Univ. of New South Wales); Matthew Drescher (UC Davis); Tony Huynh (Université Libre de Bruxelles); Abdallah Saffidine (Univ. of New South Wales) |
| 9:25-9:45 | Eulerian Graph Sparsification by Effective Resistance Decomposition Arun Jambulapati (Univ. of Washington); Sushant Sachdeva (Univ. of Toronto); Aaron Sidford (Stanford Univ.); Kevin Tian (Microsoft Research); Yibin Zhao (Univ. of Toronto) | Hiring for An Uncertain Task: Joint Design of Information and Contracts Matteo Castiglioni (Politecnico di Milano); Junjie Chen (City Univ. of Hong Kong) | An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition Pascal Koiran (LIP-ENS Lyon) | Engineering Optimal Parallel Task Scheduling Matthew Akram, Nikolai Maas, Peter Sanders, Dominik Schreiber, and Wendy Yi (Karlsruhe Institute of Technology) |
| 9:50-10:10 | A Cut-Matching Game for Constant-Hop Expanders Bernhard Haeupler (INSAIT, Sofia Univ. “St. Kliment Ohridski"); Jonas Huebotter (ETH Zurich); Mohsen Ghaffari (MIT) | A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design Matteo Castiglioni (Politecnico di Milano); Junjie Chen (City Univ. of Hong Kong); Minming Li (City Univ. of Hong Kong); Haifeng Xu (Univ. of Chicago); Song Zuo (Google Research) | Improving the Leading Constant of Matrix Multiplication Hantao Yu (Columbia Univ.); Josh Alman (Columbia Univ.) | Another L Makes It Better? Lagrange Meets LLL and May Improve BKZ Pre-Processing Sebastien Balny (Université de Picardie Jules Verne); Claire Delaplace and Gilles Dequen (Université de Picardie Jules Verne) |
| 10:15-10:35 | Quasilinear-Time Eccentricities Computation, and More, on Median Graphs Pierre Bergé (Université Clermont Auvergne); Ducoffe Guillaume (Univ. of Bucharest); Habib Michel (Université Paris Cité) | Majorized Bayesian Persuasion and Fair Selection Siddhartha Banerjee (Cornell Univ.); Kamesh Munagala and Yiheng Shen (Duke Univ.); Kangning Wang (Rutgers Univ.) | Faster Linear Systems and Matrix Norm Approximation Via Multi-Level Sketched Preconditioning Michal Derezinski (UMich); Christopher Musco (NYU); Jiaming Yang (UMich) | HyperSteiner: Computing Heuristic Hyperbolic Steiner Minimal Trees Aniss A. Medbouhi (KTH Royal Institute of Technology); Alejandro García-Castellanos (VU Univ. Amsterdam); Giovanni Luca Marchetti and Danica Kragic (KTH Royal Institute of Technology); Erik Johannes Bekkers (Univ. of Amsterdam) |
| 10:40-11:00 | Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal Daoyuan Chen and Simon Meierhans (ETH Zurich); Maximilian Probst Gutenberg; Thatchaphol Saranurak (UMich) | Multi-Agent Combinatorial Contracts Paul Duetting (Google Research); Tomer Ezra (Harvard Univ.); Michal Feldman (Tel Aviv Univ.); Thomas Kesselheim (Univ. of Bonn) | More Asymmetry Yields Faster Matrix Multiplication Josh Alman (Columbia Univ.); Ran Duan (Tsinghua Univ.); Virginia Vassilevska Williams, Yinzhan Xu, and Zixuan Xu (MIT); Renfei Zhou (CMU) | A Greedy Algorithm for Low-Crossing Partitions for General Set Systems Monika Csikos and Alexandre Louvet; Nabil Mustafa (Université Sorbonne Paris Nord) |
| 11:05 AM - 11:30 AM | Coffee Break | Grand Gallery - 2nd Floor |
|---|---|---|
| 11:30 AM - 12:45 PM | CP17 SODA Best Paper and Best Student Paper Prize Session | Grand Ballroom C/D - 2nd Floor |
| 12:45 PM - 2:00 PM | Lunch Break | Attendees on their own |
| Time | SODA 5A Grand Ballroom C/D - 2nd Floor Chair: Sanjeev Khanna (UPenn) | SODA 5B Toulouse - 2nd Floor Mezzanine Chair: R Ravi (CMU) | SODA 5C Grand Ballroom A - 2nd Floor Chair: Emily Fox (Univ. of Texas at Dallas) | SOSA1 St. Charles - 1st Floor Chair: Iona Bercea (KTH Royal Institute of Technology) |
|---|---|---|---|---|
| 2:00-2:20 | A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs Chandra Chekuri and Rhea Jain (UIUC) | Testing Approximate Stationarity Concepts for Piecewise Affine Functions Lai Tian (The Chinese Univ. of Hong Kong); Anthony So (Chinese Univ. of Hong Kong) | Flipping Non-Crossing Spanning Trees Birgit Vogtenhuber (Graz Univ. of Technology); Håvard Bjerkevik (Univ. at Albany); Linda Kleist (Univ. of Potsdam); Torsten Ueckerdt (Karlsruhe Institute of Technology) | Simple Sublinear Algorithms for (Delta + 1) Vertex Coloring Via Asymmetric Palette Sparsification Sepehr Assadi and Helia Yazdanyar (Univ. of Waterloo) |
| 2:25-2:45 | Congestion-Approximators from the Bottom Up Jason M. Li (CMU) | Forall-Exist Statements in Pseudopolynomial Time Eleonore Bach (EPFL); Friedrich Eisenbrand (École Polytechnique Fédérale de Lausanne); Thomas Rothvoss (Univ. of Washington); Robert Weismantel (ETH Zurich) | Ptases for Euclidean Tsp with Unit Disk and Unit Square Neighborhoods William Lochet (CNRS); Sayan Bandyapadhyay (Portland State Univ.); katie clinch (Univ. of New South Wales); Daniel Lokshtanov (UC Santa Barbara); Saket Saurabh (Institute of Mathematical Sciences and Univ. of Bergen); Jie Xue (NYU-Shanghai) | How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing John M. Kallaugher and Ojas Parekh (Sandia National Laboratories); Nadezhda Voronova (Boston Univ.) |
| 2:50-3:10 | (Almost) Ruling Out Seth Lower Bounds for All-Pairs Max-Flow Ohad Trabelsi (Toyota Technological Institute at Chicago) | Complexity of Polytope Diameters Via Perfect Matchings Christian Nöbel and Raphael Steiner (ETH Zurich) | Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching Sujoy Bhore (IIT Bombay); Timothy M. Chan (UIUC) | Sublinear-Time Algorithm for MST-Weight Revisited Gryphon Patlin and Jan van den Brand (Georgia Institute of Technology) |
| 3:15-3:35 | Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and All Eccentricities in Graphs Feodor F. Dragan (Kent State Univ.); Guillaume Ducoffe (ICI – National Institute for Research and Development informatics); Michel Habib (Université Paris); Laurent Viennot (Inria) | The Change-of-Measure Method, Block Lewis Weights, and Approximating Matrix Block Norms Naren S. Manoj and Max Ovsiankin (Toyota Technological Institute at Chicago) | Strict Self-Assembly of Discrete Self-Similar Fractals in the Abstract Tile Assembly Model Florent Becker (Université d'Orleans); Daniel Hader and Matthew Patitz (Univ. of Arkansas) | Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space Jakub Tetek (INSAIT, Sofia Univ. “St. Kliment Ohridski"); Christian J. Lebeda (Inria) |
| 3:40-4:00 | Flip Dynamics for Sampling Colorings: Improving Charlie A. Carlson (UC Santa Barbara); Eric Vigoda (UC Santa Barbara) | Integer Programs with Nearly Totally Unimodular Matrices: the Cographic Case Manuel Aprile (Univ. of Padova); Samuel Fiorini and Gwenaël Joret (Université Libre de Bruxelles); Stefan Kober (Université libre de Bruxelles); Michal Seweryn (Charles Univ.); Stefan Weltge (Technische Univ. München); Yelena Yuditsky (McGill Univ.) | Path and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances Yu Chen (National Univ. of Singapore); Zihan Tan (Rutgers Univ.) | On Optimal Testing of Linearity Vipul Arora (National Univ. of Singapore); Esty Kelman (Boston Univ. and MIT); Uri Meir (Tel Aviv Univ.) |
| 4:05 PM - 4:30 PM | Coffee Break | Grand Gallery - 2nd Floor |
|---|
| Time | SODA 6A Grand Ballroom C/D - 2nd Floor Chair: R Ravi (CMU) | SODA 6B Toulouse - 2nd Floor Mezzanine Chair: Karthik CS (Rutgers Univ.) | SODA 6C Grand Ballroom A - 2nd Floor Chair: Debmalya Panigrahi (Duke Univ.) | SOSA2 St. Charles - 1st Floor Chair: Cliff Stein (Columbia Univ.) |
|---|---|---|---|---|
| 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 Univ. of Munich) | Near-Optimal Hierarchical Matrix Approximation from Matrix-Vector Products Feyza Duman Keles and Tyler Chen (NYU); Diana Halikias (Cornell Univ.); Cameron Musco (UMass); Christopher Musco (NYU); David Persson (École Polytechnique Fédérale de Lausanne) | Private Mean Estimation with Person-Level Differential Privacy Rose Silver (CMU); Sushant Agarwal (Northeastern Univ.); Gautam Kamath (Univ. of Waterloo); Mahbod Majid (MIT); Argyris Mouzakis (Univ. of Waterloo); Jonathan Ullman (Northeastern Univ.) | A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations William Kuszmaul (MIT) |
| 4:55-5:15 | Approximating Competitive Equilibrium by Nash Welfare Jugal Garg (UIUC); Yixin Tao (Shanghai Univ. of Finance and Economics); László Végh (Bonn Univ.) | Improved Spectral Density Estimation Via Explicit and Implicit Deflation Rajarshi Bhattacharjee (UMass); Rajesh Jayaram (Google Research); Cameron Musco (UMass); Christopher Musco (NYU); Archan Ray (Memorial Sloan-Kettering Cancer Center) | Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions Jane Lange (MIT); Ephraim Linder and Sofya Raskhodnikova (Boston Univ.); Arsen Vasilyan (Michigan State Univ.) | Only Two Shuffles Perform Card-Based Zero-Knowledge Proof for Sudoku of Any Size Kodai Tanaka (Tohoku Univ.); Shun Sasaki and Kazumasa Shinagawa (Ibaraki Univ.); Takaaki Mizuki (Tohoku Univ.) |
| 5:20-5:40 | Tolls for Dynamic Equilibrium Flows Julian Schwarz, Tobias Harks, and Lukas Graf (Univ. of Passau) | On the Decidability of Presburger Arithmetic Expanded with Powers Toghrul Karimov (Max Planck Institute for Software Systems); Florian Luca (Stellenbosch Univ.); Joris Nieuwveld and Joël Ouaknine (Max Planck Institute for Software Systems); James Worrell (Univ. of Oxford) | Almost Tight Bounds for Differentially Private Densest Subgraph Michael Dinitz (Johns Hopkins Univ.); Satyen Kale (Apple); Silvio Lattanzi (Google Zurich); Sergei Vassilvitskii (Google Research) | A Multilinear Johnson-Lindenstrauss Transform Antonis Matakos, Petteri Kaski, and Heikki Mannila (Aalto Univ.) |
| 5:45-6:05 | Platforms for Efficient and Incentive-Aware Collaboration Kunhe Yang (UC Berkeley); Nika Haghtalab (Lawrence Berkeley National Laboratory and UC Berkeley); Mingda Qiao (Univ. of St. Gallen and UC Berkeley) | Solving Polynomial Equations Over Finite Fields Holger Dell (IT Univ. of Copenhagen); Anselm Haak (Univ. of Paderborn); Melvin Kallmayer (Goethe Univ. Frankfurt); Leo Wennmann (Maastricht Univ.) | Improved Differentially Private Continual Observation Using Group Algebra Jalaj Upadhyay (Rutgers Univ.); Monika Henzinger (Institute of Science and Technology Austria) | Better Gaussian Mechanism Using Correlated Noise Christian J. Lebeda (Inria) |
| 6:10-6:30 | Clock Auctions Augmented with Unreliable Advice Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan (Drexel Univ.) | Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture Andreas Björklund (IT Univ. of Copenhagen); Kevin Pratt (NYU); Petteri Kaski (Aalto Univ.); Thore Husfeldt (IT Univ. of Copenhagen); Radu Curticapean (Univ. of Regensburg and IT Univ. of Copenhagen) | Ellipsoid Fitting Up to Constant Via Empirical Covariance Estimation June Wu (Univ. of Chicago); Madhur Tulsiani (Toyota Technological Institute at Chicago) |
| 6:45 PM - 7:45 PM | SODA Business Meeting & Awards Presentation, followed by SOSA Business Meeting (Complimentary beer and wine will be served) | Grand Ballroom C/D - 2nd Floor |
|---|