SODA23 Accepted Papers | SIAM

Accepted Papers

Visualizer: Accepted Papers

Paper titles and author information appears as submitted.

Paper title and author changes will not be made to this page. The online program will reflect the most up-to-date presentation details, and is scheduled for posting in November.

Small Shadows of Lattice Polytopes
Alexander Black (UC Davis)

Fair allocation of a multiset of indivisible items
Pranay Gorantla (Princeton University); Kunal Marwaha (University of Chicago); Santhoshini Velusamy (Harvard University)

Hierarchies of Minion Tests for PCSPs through Tensors
Lorenzo Ciardo and Stanislav Zivny (University of Oxford)

Approximate Graph Colouring and Crystals
Lorenzo Ciardo and Stanislav Zivny (University of Oxford)

The Price of Stability for First Price Auction
Yaonan Jin (Columbia University); Pinyan Lu (Shanghai University of Finance and Economics)

Spencer's theorem in nearly input-sparsity time
Vishesh Jain (University of Illinois Chicago); Ashwin Sah and Mehtaab Sawhney (MIT)

Spatial Mixing and the random-cluster dynamics on lattices
Reza Gheissari and Alistair Sinclair (University of California Berkeley)

Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vladut-Zink bounds
Shu Liu (University of Electronic Science and Technology of China); Wu Ting Yi (Huawei); Chaoping Xing (Shanghai Jiao Tong University)

A Near-Linear Time Sampler for the Ising Model with External Field
Xiaoyu Chen and Xinyuan Zhang (Nanjing University)

Concentration of polynomial random matrices via Efron-Stein inequalities
Goutham Rajendran (University of Chicago); Madhur Tulsiani (Toyota Technological Institute at Chicago)

Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and kmismatch Matching
Ce Jin (MIT); Jakob Nogler (ETH Zurich)

Halving by a Thousand Cuts or Punctures
Sariel Har-Peled and Da Wei Zheng (University of Illinois Urbana-Champaign)

On the number incidences when avoiding an induced biclique in geometric settings
Timothy M. Chan and Sariel Har-Peled (University of Illinois at Urbana-Champaign)

Subexponential mixing for partition chains on grid-like graphs
Alan Frieze and Wesley Pegden (Carnegie Mellon University)

Weisfeiler–Leman and Graph Spectra
Gaurav Rattan and Tim Seppelt (RWTH Aachen University)

Stronger 3SUM-Indexing Lower Bounds
Eldon Chung (Center for Quantum Technologies); Kasper Green Larsen (Aarhus University)

Tight Bounds for Monotone Minimal Perfect Hashing
Sepehr Assadi and Martin Farach-Colton (Rutgers University); William Kuszmaul (MIT)

Almost Consistent Systems of Linear Equations
Konrad K. Dabrowski (Newcastle University); Peter Jonsson (Linköping University); Sebastian Ordyniak (University of Leeds); George Osipov (Linköping University); Magnus Wahlström (Royal Holloway University of London)

Testing and Learning Quantum Juntas Nearly Optimally
Thomas Chen, Shivam Nadimpalli, and Henry Yuen (Columbia University)

Testing Convex Truncation
Anindya De (University of Pennsylvania); Shivam Nadimpalli and Rocco A. Servedio (Columbia University)

Player-optimal Stable Regret for Bandit Learning in Matching Markets
Fang Kong and Shuai Li (Shanghai Jiao Tong University)

Competitive Information Design for Pandora’s Box
Bolin Ding (Alibaba Group); Yiding Feng (Microsoft Research); Chien-Ju Ho (Washington University in St. Louis); Wei Tang (Columbia University); Haifeng Xu (University of Chicago)

Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
Dominik Kempa (Stony Brook University); Tomasz Kociumaka (Max Planck Institute for Informatics)

Short Synchronizing Words for Random Automata
Guillaume Chapuy (Université Paris Cité, CNRS, IRIF, F-75013, Paris, France); Guillem Perarnau (Universitat Politècnica de Catalunya)

Packing cycles in planar and bounded-genus graphs
Niklas Schlomberg (University of Bonn); Hanjo Thiele (Greenplan GmbH, Bonn); Jens Vygen (University of Bonn)

Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
Peter Davies (Durham University)

Optimal Fully Dynamic $k$-Center Clustering for Adaptive and Oblivious Adversaries
MohammadHossein Bateni, Hossein Esfandiari, and Hendrik Fichtenberger (Google Research); Monika Henzinger (University of Vienna); Rajesh Jayaram and Vahab Mirrokni (Google Research); Andreas Wiese (Technical University of Munich)

A logic-based algorithmic meta-theorem for mim-width
Jan Dreier (TU Wien); Benjamin Bergougnoux and Lars Jaffke (University of Bergen)

Tiny Pointers
Michael Bender (Stony Brook University); Alex Conway (Vmware Research); Martin Farach-Colton (Rutgers University); William Kuszmaul (MIT); Guido Tagliavini (Rutgers University)

Streaming complexity of CSPs with randomly ordered constraints
Raghuvansh R. Saxena (Microsoft Research); Noah Singer (CMU); Madhu Sudan and Santhoshini Velusamy (Harvard University)

Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal (Indian Institute of Technology Madras); Daniel Marx (CISPA Helmholtz Center for Information Security); Daniel Neuen (Simon Fraser University); Jasper Slusallek(Saarland University)

Near-Linear Time Approximations for Cut Problems via Fair Cuts
Jason Li (UC Berkeley); Danupon Nanongkai (University of Copenhagen); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (University of Michigan)

Stronger Privacy Amplification by Shuffling for R\'enyi and Approximate DifferentialPrivacy
Audra McMillan, Kunal Talwar, and Vitaly Feldman (Apple)

Minimizing Completion Times for Stochastic Jobs via Batched Free Times
Anupam Gupta (Carnegie Mellon); Benjamin Moseley and Rudy Zhou (Carnegie Mellon University)

Optimal Pricing Schemes for an Impatient Buyer
Yuan Deng, Jieming Mao, and Balasubramanian Sivan (Google Research); Kangning Wang (Duke University)

Online Prediction in Sub-linear Space
Binghui Peng (Columbia); Fred Zhang (UC Berkeley)

Fast Discrepancy Minimization with Hereditary Guarantees
Kasper Green Larsen (Aarhus University)

Exact Flow Sparsification Requires Unbounded Size
Robert Krauthgamer and Ron Mosenzon (Weizmann Institute of Science)

Curve Simplification and Clustering under Frechet Distance
Siu-Wing Cheng and Haoqiang Huang (HKUST)

Almost Tight Bounds for Online Facility Location in the Random-Order Model
Haim Kaplan (Tel Aviv University); David Naori (Computer Science Department, Technion); Danny Raz (Technion)

The complete classification for quantified equality constraints
Dmitriy Zhuk (Charles University); Barnaby Martin (Durham University); Michal Wrona (Jagiellonian University)

Small subgraphs with large average degree
Oliver Janzer (University of Cambridge); Benny Sudakov (ETH Zurich); István Tomon (Umea University)

Mean estimation when you have the source code; or, quantum Monte Carlo methods
Robin Kothari (Microsoft Quantum); Ryan O'Donnell (Carnegie Mellon University)

Online Min-Max Paging
Ashish Chiplunkar (Indian Institute of Technology Delhi); Monika Henzinger, Sagar Sudhir Kale, and Maximilian Vötsch (University of Vienna)

Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and BicoloredEuclidean Travelling Salesman Tours
François Dross (Univ. Bordeaux, CNRS, Bordeaux INP, LaBRI, France); Krzysztof Fleszar (University of Warsaw, Poland); Karol Wegrzycki (Saarland University and Max Planck Institute for Informatics, Germany); Anna Zych-Pawlewicz (University of Warsaw, Poland)

Map matching queries on realistic input graphs under the Fréchet distance
Joachim Gudmundsson, Martin P. Seybold, and Sampson Wong (University of Sydney)

Private Query Release via the Johnson Lindenstrauss Transform
Aleksandar Nikolov (University of Toronto)

Efficient decoding up to a constant fraction of the code length for asymptotically goodquantum codes
Anthony Leverrier (Inria Paris); Gilles Zémor (University of Bordeaux)

Passing the Limits of Pure Local Search for weighted k-Set Packing
Meike Neuwohner (Research Institute for Discrete Mathematics, University of Bonn)

Improved Bounds for Sampling Solutions of Random CNF Formulas
Kun He (Chinese Academy of Sciences); Kewen Wu (University of California, Berkeley); Kuan Yang (Shanghai Jiao Tong University)

Pricing Query Complexity of Revenue Maximization
Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah (GoogleResearch)

Flow-augmentation III: complexity dichotomy for Boolean CSPs parameterized by thenumber of unsatisfied constraints
Eun Jung Kim (LAMSADE, Paris-Dauphine University); Stefan Kratsch (HU Berlin); Marcin Pilipczuk (University of Warsaw); Magnus Wahlstrom (Royal Holloway University of London)

Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterizedby the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel (National Institute of Informatics, Tokyo, Japan); Lars Jaffke (Department of Informatics, University of Bergen, Bergen, Norway); Paloma T. Lima (IT University of Copenhagen, Denmark); Tomáš Masařìk (University of Warsaw, Poland); Marcin Pilipczuk (University of Warsaw); Roohani Sharma (Max Planck Institute for Informatics, Germany); Manuel Sorge (TU Wien)

Approximate Trace Reconstruction from a Single Trace
Xi Chen (Columbia University); Anindya De (University of Pennsylvania); Chin Ho Lee (Harvard University); Rocco Servedio and Sandip Sinha (Columbia University)

Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
Sayan Bhattacharya and Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan)

Sharp threshold sequence and universality for Ising perceptron models
Shuta Nakajima (Meiji University); Nike Sun (Massachusetts Institute of Technology)

Maintaining Expander Decompositions via Sparse Cuts
Rasmus Kyng, Maximilian Probst Gutenberg, Yiding Hua, and Zihang Wu (ETH Zurich)

Near Optimal Analysis of the Cube versus Cube Test
Dor Minzer and Kai Zhe Zheng (MIT)

Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, and Xiao Mao (Massachusetts Institute of Technology)

Online and Bandit Algorithms for Norms with Gradient-Stable Approximations
Thomas Kesselheim (University of Bonn); Marco Molinaro (Microsoft Research and PUCRio); Sahil Singla (Georgia Tech)

On complex roots of the independence polynomial
Ferenc Bencs (Korteweg de Vries Institute for Mathematics, University of Amsterdam); Péter Csikvári (Alfréd Rényi Institute of Mathematics and Eötvös Loránd University); Piyush Srivastava (Tata Institute of Fundamental Research); Jan Vondrák (Stanford University)

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
Timothy M. Chan and Da Wei Zheng (UIUC)

Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Parinya Chalermsook (Aalto University); Manoj Gupta (IIT Gandhinagar); Wanchote Jiamjitrak and Nidia Obscura Acosta (Aalto University); Akash Pareek (IIT Gandhinagar); Sorrachai Yingchareonthawornchai (Aalto University)

Moser-Tardos Algorithm: Beyond Shearer's Bound
Kun He, Qian Li, and Xiaoming Sun (Institute of Computing Technology, Chinese Academy of Sciences)

Deterministic counting Lovasz local lemma beyond linear programming
Kun He (ICT,CAS); Chunyang Wang and Yitong Yin (Nanjing University)

Conflict-free hypergraph matchings
Stefan Glock (ETH Zürich); Felix Joos and Marcus K\"uhn (Universität Heidelberg); Jaehoon Kim (KAIST); Lyuben Lichev (Université Jean Monnet and Institut Camille Jordan, Saint-Etienne)

A Subquadratic $n^\epsilon$-approximation for the Continuous Fréchet Distance Thijs
van der Horst (Utrecht University / TU Eindhoven); Marc van Kreveld (Utrecht University); Tim Ophelders (Utrecht University / TU Eindhoven); Bettina Speckmann (TU Eindhoven)

Interdependent Public Projects
Avi Cohen (StarkWare Industries Ltd.); Michal Feldman and Divyarthi Mohan (Tel Aviv University); Inbal Talgam-Cohen (Technion - Israel Institute of Technology)

A Nearly Time-Optimal Distributed Approximation of Minimum Cost $k$-Edge-Connected Spanning Subgraph
Michal Dory (ETH Zurich & Haifa University); Mohsen Ghaffari (MIT)

A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke (University of Bergen, Norway); Paloma T. Lima (IT University of Copenhagen, Denmark); Tomáš Masařìk and Marcin Pilipczuk (University of Warsaw, Poland); Ueverton S. Souza (Fluminense Federal University, Brazil and University of Warsaw, Poland)

Polynomial formulations as a barrier for reduction-based hardness proofs
Tatiana Belova (Steklov Institute of Mathematics at St. Petersburg); Alexander Golovnev (Georgetown University); Alexander Kulikov (Steklov Institute of Mathematics at St. Petersburg); Ivan Mihajlin (Leonhard Euler International Mathematical Institute in St. Petersburg); Denil Sharipov (St. Petersburg State University)

Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth
Krishnendu Chatterjee (IST Austria); Tobias Meggendorfer (ISTA); Raimundo Saona and Jakub Svoboda (IST Austria)

Instability of backoff protocols with arbitrary arrival rates
Leslie Ann Goldberg (Department of Computer Science, University of Oxford); John Lapinskas (Department of Computer Science, University of Bristol)

On the orbit closure intersection problems for matrix tuples under conjugation and leftright actions
G\'abor Ivanyos (Institute for Computer Science and Control, E\"otv\"os Lor\'and Research Network (ELKH), Budapest, Hungary); Youming Qiao (University of Technology Sydney)

Constant Approximating Parameterized k-SetCover is W[2]-hard
Bingkai Lin (Nanjing University); Xuandi Ren (University of California, Berkeley); Yican Sun (Peking University); Xiuhan Wang (Tsinghua University)

Online Lewis Weight Sampling
David P. Woodruff and Taisuke Yasuda (Carnegie Mellon University)

Toeplitz Low-Rank Approximation with Sublinear Query Complexity
Michael Kapralov (EPFL); Hannah Lawrence (MIT); Mikhail Makarov (EPFL); Cameron Musco (University of Massachusetts Amherst); Kshiteej Sheth (EPFL)

Kernelization for Graph Packing Problems via Rainbow Matching
Stéphane Bessy, Marin Bougeret, Dimitrios Thilikos, and Sebastian Wiederrecht (LIRMM, Univ Montpellier, CNRS, Montpellier, France)

Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
Penny Haxell (University of Waterloo); Tibor Szabó (Freie Universität Berlin)

Generalized Unrelated Machine Scheduling Problem
Shichuan Deng and Jian Li (Tsinghua University); Yuval Rabani (Hebrew University)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-TreewidthGraphs
Jacob Focke, Dániel Marx, and Fionn Mc Inerney (CISPA Helmholtz Center for Information Security); Daniel Neuen (Simon Fraser University); Govind Sankar (Duke University); Philipp Schepper (CISPA Helmholtz Center for Information Security); Philip Wellnitz (Max Planck Institute for Informatics, SIC)

An Improved Approximation for Maximum Weighted k-Set Packing
Theophile Thiery and Justin Ward (Queen Mary University of London)

Excluding Single-Crossing Matching Minors in Bipartite Graphs
Archontia Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Dimitrios M. Thilikos and Sebastian Wiederrecht (LIRMM, Univ Montpellier, CNRS, Montpellier, France)

Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
Shang-En Huang, Seth Pettie, and Leqi Zhu (University of Michigan)

Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
Timothy M. Chan (University of Illinois at Urbana-Champaign)

Simple, deterministic, fast (but weak) approximations to edit distance and Dyck editdistance
Michal Koucký (Charles University); Michael Saks (Rutgers Unviersity)

From algorithms to connectivity and back: finding a giant component in random k-SAT
Zongchen Chen and Nitya Mani (MIT); Ankur Moitra (Math & CSAIL, MIT)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy (CNRS, LaBRI, Université de Bordeaux, Bordeaux, France); Édouard Bonnet and Hugues Déprés (Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France); Louis Esperet (CNRS, G-SCOP, Univ. Grenoble Alpes, Grenoble, France.); Colin Geniet (Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France); Claire Hilaire (CNRS, LaBRI, Université de Bordeaux, Bordeaux, France); Stéphan Thomassé (Univ Lyon, CNRS, ENS de Lyon,Université Claude Bernard Lyon 1, LIP UMR5668, France); Alexandra Wesolek (Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada)

Shrunk subspaces via operator Sinkhorn iteration
Cole Franks, Tasuku Soma, and Michel Goemans (MIT)

Improved Approximation Algorithms for Unrelated Machines
Sungjin Im (University of California Merced); Shi Li (University at Buffalo)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper MinorClosed Graph Classes
Petr A. Golovach (Department of Informatics, University of Bergen, Norway); Giannos Stamoulis and Dimitrios M. Thilikos (LIRMM, Univ Montpellier, CNRS, Montpellier, France)

A Distanced Matching Game, Decremental APSP in Expanders, and Faster DeterministicAlgorithms for Graph Cut Problems
Julia Chuzhoy (Toyota Technological Institute at Chicago)

Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
Yaonan Jin (Columbia University); Daogao Liu (University of Washington); Zhao Song (Adobe Research)

A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function
Tsuyoshi Hirayama (Kyoto University); Yuhao Liu (University of Electronic Sciences and Technology); Kazuhisa Makino (Kyoto University); Ke Shi and Chao Xu (University of Electronic Sciences and Technology)

Positivity of the symmetric group characters is PH-hard
Christian Ikenmeyer (University of Liverpool); Igor Pak (University of California, Los Angeles); Greta Panova (University of Southern California)

Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth
nairen cao and Jeremy Fineman (Georgetown University)

On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem
Mong-Jen Kao (National Yang-Ming Chiao-Tung University, Taiwan.)

Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is2-ExpTime-Complete
Stefan Göller (University of Kassel); Paweł Parys (University of Warsaw)

Beating Greedy Matching in Sublinear Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi (Stanford University)

Integrality Gaps for Random Integer Programs via Discrepancy
Daniel Dadush and Sander Borst (CWI Amsterdam); Dan Mikulincer (MIT)

Improved Approximation for Two-Edge-Connectivity
Mohit Garg (Universitat Bremen); Fabrizio Grandoni (IDSIA); Afrouz Jabal Ameli (TU Eindhoven)

Zigzagging through acyclic orientations of chordal graphs and hypergraphs
Jean Cardinal (Université Libre de Bruxelles); Hung Hoang (ETH Zurich); Arturo Merino (Technische Universität Berlin); Torsten Mütze (University of Warwick)

Shortest Cycles With Monotone Submodular Costs
Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen (University of Bergen); Daniel Lokshtanov (University of California Santa Barbara); Giannοs Stamoulis (LIRMM, Université de Montpellier, CNRS)

Traversing the FFT Computation Tree for Dimension-Independent Sparse FourierTransforms
Mikhail Makarov (École polytechnique fédérale de Lausanne); Karl Bringmann (Saarland University); Michael Kapralov (EPFL); Vasileios Nakos (RelationalAI); Amir Zandieh (EPFL); Amir Yagudin (MIPT)

Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen (University of Bergen); Kirill Simonov (TU Wien); Giannοs Stamoulis (LIRMM, Université de Montpellier, CNRS)

A half-integral Erd\H{o}s-P\'osa theorem for directed odd cycles
Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin); O-joung Kwon (Hanyang University and Institute for Basic Science); Qiqin Xie (Shanghai University)

Improved Bi-point Rounding Algorithms and a Golden Barrier for $k$-Median
Kishen N Gowda (University of Maryland); Thomas Pensyl (unaffiliated); Aravind Srinivasan (University of Maryland); Khoa Trinh (Google)

Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
Hung Le (University of Massachusetts Amherst)

A Framework for Approximation Schemes on Disk Graphs
Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (IIT Hyderabad, India); Saket Saurabh (IMSc); Jie Xue (New York University Shanghai); Meirav Zehavi (Ben-Gurion University)

Cubic Goldreich-Levin
Anqi Li (MIT); Jonathan Tidor (Massachusetts Institute of Technology); Dain Kim (Massachusetts Institute of Technology Mathematics department)

Closing the Gap Between Directed Hopsets and Shortcut Sets
Aaron Bernstein (Rutgers University); Nicole Wein (DIMACS, Rutgers University)

``Who is Next in Line?" On the Significance of Knowing the Arrival Order in Bayesian OnlineSettings
Tomer Ezra (Sapienza University of Rome); Michal Feldman (Tel Aviv University); Nick Gravin and Zhihao Gavin Tang (Shanghai University of Finance and Economics)

Smaller Low-Depth Circuits for Kronecker Powers
Josh Alman, Yunfeng Guan, and Ashwin Padaki (Columbia University)

Fast algorithms for solving the Hamilton Cycle problem with high probability
Michael Anastos (Institute of Science and Technology of Austria)

On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and TrianglarStructured ILPs
Kim-Manuel Klein (Bremen University); Adam Polak (EPFL); Lars Rohwedder (Maastricht University)

Maximal k-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
Chaitanya Nalam and Thatchaphol Saranurak (University of Michigan)

A simple and sharper proof of the hypergraph Moore bound
Jun-Ting Hsieh and Pravesh K. Kothari (Carnegie Mellon University); Sidhanth Mohanty (University of California Berkeley)

A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
Yassine Hamoudi (UC Berkeley); Arjan Cornelissen (QuSoft, University of Amsterdam)

On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
Mingyang Deng, Xiao Mao, and Ziqian Zhong (Massachusetts Institute of Technology)

Query Complexity of the Metric Steiner Tree Problem
Yu Chen and Sanjeev Khanna (University of Pennsylvania); Zihan Tan (University of Chicago)

Sublinear-Time Algorithms for Max Cut, Max E2Lin$(q)$, and Unique Label Cover on Expanders
Pan Peng (University of Science and Technology of China); Yuichi Yoshida (National Institute of Informatics)

Near-Linear Sample Complexity for $L_p$ Polynomial Regression
Raphael A. Meyer (New York University); Cameron Musco (University of Massachusetts Amherst); Christopher Musco (New York University); David P. Woodruff and Samson Zhou (Carnegie Mellon University)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
Calum MacRury (University of Toronto); Will Ma (Columbia University); Nathaniel Grammel (University of Maryland, College Park)

Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Yeshwanth Cherapanamjeri (UC Berkeley); Sandeep Silwal (MIT); David P. Woodruff and Samson Zhou (Carnegie Mellon University)

Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
Taihei Oki (The University of Tokyo); Tasuku Soma (MIT)

Almost Tight Error Bounds on Differentially Private Continual Counting
Monika Henzinger (University of Vienna); Jalaj Upadhyay (Rutgers University); Sarvagya Upadhyay (Fujitsu Research of America)

Secretary Problems: The Power of a Single Sample
Pranav Nuti and Jan Vondrak (Stanford)

Robust Voting Rules from Algorithmic Robust Statistics
Allen Liu (MIT); Ankur Moitra (Math & CSAIL, MIT)

Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Cover
Shimon Kogan and Merav Parter (Weizmann)

Improved girth approximation in weighted undirected graphs
Avi Kadaria (Bar-Ilan University); Liam Roditty (Bar Ilan University); Aaron Sidford (Stanford University); Virginia Vassilevska Williams (MIT); Uri Zwick (Tel Aviv University)

Online Sorting and Translational Packing of Convex Polygons
Anders Aamand (MIT); Mikkel Abrahamsen (University of Copenhagen, Denmark); Lorenzo Beretta (University of Copenhagen); Linda Kleist (TU Braunschweig)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
Gramoz Goranci (University of Glasgow); Monika Henzinger (University of Vienna); Danupon Nanongkai (University of Copenhagen); Thatchaphol Saranurak (University of Michigan); Mikkel Thorup (University of Copenhagen); Christian Wulff-Nilsen (Department of Computer Science, University of Copenhagen)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
Siddharth Bhandari (Simons Institute for the Theory of Computing); Prahladh Harsha (Tata Institute of Fundamental Research); Mrinal Kumar (IIT Bombay); Ashutosh Shankar (Tata Institute of Fundamental Research)

A Nearly Tight Analysis of Greedy k-means++
Jakub Tetek (Basic Algorithms Research Copenhagen, University of Copenhagen); Christoph Grunau, Václav Rozhoň, and Ahmet Alper Özüdoğru (ETH Zurich)

A polynomial-time algorithm for 1/2-well-supported Nash equilibria in bimatrix games
Argyrios Deligkas (Royal Holloway, University of London); Michail Fasoulakis (Foundation for Research and Technology-Hellas (FORTH)); Evangelos Markakis (Athens University of Economics and Business)

Bidder subset selection problem in auction design
Xiaohui Bei (Nanyang Technological University); Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang (Shanghai University of Finance and Economics)

Massively Parallel Computation on Embedded Planar Graphs
Jakub Tetek and Jacob Holm (Basic Algorithms Research Copenhagen, University of Copenhagen)

Balanced Allocations: The Power of Memory with Heterogeneous Bins
Dimitrios Los and Thomas Sauerwald (University of Cambridge); John Sylvester (University of Glasgow)

Simple Mechanisms for Agents with Non-linear Utilities
Yiding Feng (Microsoft Research); Jason D. Hartline (Northwestern University); Yingkai Li (Yale University)

The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay
Ngoc Mai Le, Seeun William Umboh, and Ningyuan Xie (The University of Sydney)

Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Ruoxu Cen and William He (Duke University); Jason Li (UC Berkeley); Debmalya Panigrahi (Duke University)

Discrepancy minimization via regularization
Lucas Pesenti (Bocconi University); Adrian Vladu (CNRS & IRIF, Université Paris Cité)

Equivalence Test for Read-Once Arithmetic Formulas
Nikhil Gupta (Indian Institute of Science, Bangalore); Chandan Saha (IISc Bangalore); Bhargav Thankey (Indian Institute of Science, Bangalore)

Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
Xin Lyu (University of California, Berkeley); Weihao Zhu (Shanghai Jiao Tong University)

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
Salwa Faour (University of Freiburg); Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich); Fabian Kuhn (University of Freiburg); Václav Rozhoň (ETH Zurich)

Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max Coverage
Pallavi Jain and Lawqueen Kanesh (Indian Institute of Technology Jodhpur); Fahad Panolan (Department of Computer Science and Engineering, IIT Hyderabad, India); Souvik Saha (Institute of Mathematical Sciences, HBNI); Abhishek Sahu (National Institute of Science Education and Research, HBNI); Saket Saurabh (Institute of Mathematical Sciences); Anannya Upasana (Institute of Mathematical Sciences, HBNI)

Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Mohsen Ghaffari (MIT); Christoph Grunau (ETH Zurich); Bernhard Haeupler (ETH Zurich & CMU); Saeed Ilchi and Václav Rozhoň (ETH Zurich)

Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to kMedian
Vincent Cohen-Addad (Google); Fabrizio Grandoni (IDSIA, University of Lugano); Euiwoong Lee (University of Michigan); Chris Schwiegelshohn (Aarhus University)

Query Complexity of Inversion Minimization on Trees
Ivan Hu, Dieter van Melkebeek, and Andrew Morgan (University of Wisconsin-Madison)

Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths
Shiri Chechik and Tianyi Zhang (Tel Aviv University)

Optimal Square Detection Over General Alphabets
Jonas Ellert (Technical University of Dortmund); Pawel Gawrychowski (University of Wroclaw); Garance Gourdel (DI/ENS, PSL Research University and IRISA Inria Rennes)

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Justin Y. Chen (MIT); Badih Ghazi and Ravi Kumar (Google); Pasin Manurangsi (Google Research); Shyam Narayanan (Massachusetts Institute of Technology); Jelani Nelson (UC Berkeley & Google Research); Yinzhan Xu (MIT)

Faster Computation of 3-Edge-Connected Components in Digraphs
Loukas Georgiadis (University of Ioannina, Greece); Evangelos Kipouridis (BARC, University of Copenhagen, Universitetsparken 1, Copenhagen, Denmark); Charis Papadopoulos (University of Ioannina, Greece); Nikos Parotsidis (Google Research, Switzerland)

Sampling Equilibria: Fast No-Regret Learning in Structured Games
Daniel Beaglehole, Max Hopkins, Daniel Kane, Sihan Liu, and Shachar Lovett (UCSD)

Higher degree sum-of-squares relaxations robust against oblivious outliers
Tommaso d'Orsi, Rajai Nasser, Gleb Novikov, and David Steurer (ETH Zurich)

Fast Distributed Brooks Theorem
Manuela Fischer (ETH Zurich); Magnús Halldórsson (Reykjavik University); Yannic Maus (TU Graz)

Graph Classes With Few Minimal Separators. I. Finite Forbidden Subgraphs
Peter Gartland and Daniel Lokshtanov (University of California, Santa Barbara)

Optimal Deterministic Massively Parallel Connectivity on Forests
Alkida Balliu (Gran Sasso Science Institute); Rustam Latypov (Aalto University); Yannic Maus (TU Graz); Dennis Olivetti (Gran Sasso Science Institute); Jara Uitto (Aalto University)

Foundations of Transaction Fee Mechanism Design
Hao Chung and Elaine Shi (Carnegie Mellon University)

Graph Classes With Few Minimal Separators. II. A Dichotomy
Peter Gartland and Daniel Lokshtanov (University of California Santa Barbara, USA)

Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Alkida Balliu (Gran Sasso Science Institute); Sebastian Brandt (CISPA Helmholtz Center for Information Security); Fabian Kuhn (University of Freiburg); Dennis Olivetti (Gran Sasso Science Institute)

Quantum tomography using state-preparation unitaries
JORAN VAN APELDOORN (CWI); Arjan Cornelissen (QuSoft - University of Amsterdam); András Gilyén (Renyi Institute Budapest); Giacomo Nannicini (IBM Quantum)

Almost-Linear Planted Cliques Elude the Metropolis Process
Zongchen Chen, Elchanan Mossel, and Ilias Zadik (MIT)

Timeliness Through Telephones
Da Qi Chen (University of Virginia); Lin An, Aidin Niaparast, R. Ravi, and Oleksandr Rudenko (Carnegie Mellon University)

Efficient resilient functions
Peter Ivanov and Emanuele Viola (Northeastern); Raghu Meka (University of California, Los Angeles)

Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
Sayan Bhattacharya and Peter Kiss (University of Warwick); Thatchaphol Saranurak (University of Michigan, Ann Arbor); David Wajc (Stanford University)

The Need for Seed (in the abstract Tile Assembly Model)
Andrew Alseth and Matthew J. Patitz (University of Arkansas)

Private Convex Optimization in General Norms
Sivakanth Gopi (Microsoft Research); Yin Tat Lee, Daogao Liu, and Ruoqi Shen (University of Washington); Kevin Tian (Microsoft Research)

Dynamic Algorithms for Maximum Matching Size
Soheil Behnezhad (Stanford University)

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
Yeongwoo Hwang and Joe Neeman (The University of Texas, Austin); Ojas Parekh and Kevin Thompson (Sandia National Laboratories); John Wright (The University of California, Berkeley)

A Nearly-tight Analysis of Multipass Pairing Heaps
Corwin Sinnamon and Robert E. Tarjan (Princeton University)

A Tight Analysis of Slim Heaps and Smooth Heaps
Corwin Sinnamon and Robert Tarjan (Princeton University)

Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
Niv Buchbinder (Tel Aviv university); Joseph (Seffi) Naor (Technion); David Wajc (Stanford University)

Approximation Algorithms for Steiner Tree Augmentation Problems
R. Ravi (CMU); Weizhong Zhang and Michael Zlatin (Carnegie Mellon University)

Low Degree Testing over the Reals
Vipul Arora and Arnab Bhattacharyya (National University of Singapore); Noah Fleming (Memorial University); Esty Kelman (Hebrew University and Reichman University); Yuichi Yoshida (National Institute of Informatics)

Streaming algorithms for the missing item finding problem
Manuel Stoeckl (Dartmouth College)

Economical Convex Coverings and Applications
Sunil Arya (Hong Kong University of Science and Technology); Guilherme D. da Fonseca (Aix-Marseille Université and LIS); David Mount (University of Maryland)

Interactive Coding with Small Memory
Klim Efremenko (Ben Gurion University); Bernhard Haeupler (ETHZ & Carnegie Mellon University); Yael Tauman Kalai (Microsoft Research); Gillat Kol (Princeton University); Nicolas Resch (CWI); Raghuvansh Saxena (Microsoft Research)

Non-Stochastic CDF Estimation Using Threshold Queries
Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg, and Eleanor Goh (Cornell University)

Elliptic Curve Fast Fourier Transform Part I : Low-degree extension in time O(n log n) over all finite fields
Eli Ben-Sasson and Dan Carmon (StarkWare); Swastik Kopparty (University of Toronto); David Levit (StarkWare)

Single-Pass Streaming Algorithms for Correlation Clustering
Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan (Stanford University)

A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
Er Lu Lawrence Li and Sushant Sachdeva (University of Toronto)

Superpolynomial Lower Bounds for Decision Tree Learning and Testing
Caleb Koch, Carmen Strassle, and Li-Yang Tan (Stanford University)

The $\ell_p$-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
Yi Li (Nanyang Technological University); Honghao Lin and David P. Woodruff (Carnegie Mellon University)

Beating $(1-1/e)$-Approximation for Weighted Stochastic Matching
Mahsa Derakhshan (Princeton University); Alireza Farhadi (CMU)

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut
Lijie Chen (MIT); Gillat Kol and Dmitry Paramonov (Princeton University); Raghuvansh Saxena (Microsoft Research); Zhao Song (Adobe Research); Huacheng Yu (Princeton University)

Parameterized Algorithm for the Planar Disjoint Paths Problem: Exponential in $k^2$, and Linear in $n$
Kyungjin Cho, Eunjin Oh, and Seunghyeok Oh (POSTECH)

Learning Hierarchical Cluster Structure of Graphs in Sublinear Time
Michael Kapralov and Akash Kumar (EPFL); Silvio Lattanzi (Google Research); Aida Mousavifar (Google)

The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
Xinrui Jia, Ola Svensson, and Weiqiang Yuan (EPFL)

4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
Yakov Nekrich (Michigan Technological University); Rahul Saladi (Department of Computer Science and Automation, Indian Institute of Science, India)