SODA22 Program and Abstracts | 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.

CLAP: A New Algorithm for Promise CSPs
Lorenzo Ciardo and Stanislav Zivny (University of Oxford)

A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method
Miriam Schlöter (ETH Zürich); Martin Skutella and Khai Van Tran (TU Berlin)

Private Interdependent Valuations
Alon Eden (Harvard University); Kira Goldner (Boston University); Shuran Zheng (Harvard University)

Counting Homomorphic Cycles in Degenerate Graphs
Yevgeny Levanzov (Tel Aviv University); Lior Gishboliner (ETH Zurich); Asaf Shapira (Tel Aviv University); Raphael Yuster (University of Haifa)

Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel
David Harris (University of Maryland)

Near-Optimal Quantum Algorithms for String Problems
Shyan Akmal and Ce Jin (MIT)

Online Nash Social Welfare Maximization with Predictions
Siddhartha Banerjee (Cornell University); Vasilis Gkatzelis (Drexel University); Artur Gorokh and Billy Jin (Cornell University)

Approximate Core for Committee Selection via Market Clearing
Kamesh Munagala, Kangning Wang, and Zhiyi Wang (Duke University)

Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
Aditya Jayaprakash and Mohammad Salavatipour (University of Alberta)

Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg (ETH Zurich, Department of Computer Science)

Co-evolution of Opinion and Social Tie Dynamics Towards Structural Balance
Haotian Wang, Feng Luo, and Jie Gao (Rutgers University)

Average-Case Subset Balancing Problems
Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A. Servedio (Columbia University)

Near-Optimal Explainable k-Means for All Dimensions
Moses Charikar and Lunjia Hu (Stanford University)

Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p-metrics
Vincent Cohen-Addad (Google Research, Switzerland); Karthik C. S. (Rutgers University); Euiwoong Lee (University of Michigan)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
Maximilian Probst Gutenberg (ETH Zurich); Christian Wulff Nilsen and Debarati Das (Department of Computer Science, University of Copenhagen)

Efficient generation of elimination trees and Hamilton paths on graph associahedra
Jean Cardinal (Université libre de Bruxelles (ULB)); Arturo Merino (TU Berlin); Torsten Mütze (University of Warwick)

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
Xi Chen (Columbia University); Anindya De (University of Pennsylvania); Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha (Columbia University)

The sparse parity matrix
Amin Coja-Oghlan (Goethe University); Oliver Cooley (TU Graz); Mihyun Kang (Graz University of Technology); Joon Lee and Jean Bernoulli Ravelomanana (Goethe University)

On the complexity of binary polynomial optimization over acyclic hypergraphs
Alberto Del Pia (University of Wisconsin - Madison); Silvia Di Gregorio (Technische Universität Dresden)

Pattern Matching on Grammar-Compressed Strings in Linear Time
Moses Ganardi (Max Planck Institute for Software Systems (MPI-SWS)); Paweł Gawrychowski (University of Wrocław)

On complete classes of valuated matroids
Edin Husić (London School of Economics and Political Science); Georg Loho (University of Twente); Ben Smith (University of Manchester and Heilbronn Institute for Mathematical Research); László A. Végh (London School of Economics and Political Science)

Computational hardness of the Hylland-Zeckhauser Scheme
Thomas Chen, Xi Chen, Binghui Peng, and Mihalis Yannakakis (Columbia University)

On finding exact solutions of linear programs in the oracle model
Daniel Dadush (CWI Amsterdam); László A. Végh and Giacomo Zambelli (London School of Economics and Political Science)

Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
Jacob Focke and Dániel Marx (CISPA Helmholtz Center for Information Security); Paweł Rzążewski (Warsaw University of Technology)

Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
Sepehr Assadi (Rutgers University); Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian (Stanford University)

The Complexity of Average-Case Dynamic Subgraph Counting
Monika Henzinger (University of Vienna); Andrea Lincoln and Barna Saha (UC Berkeley)

Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
Tara Abrishami, Maria Chudnovsky, and Cemil Dibek (Princeton University); Paweł Rzążewski (Warsaw University of Technology)

The Upper Bound and Optimal-Space Queries on the LZ-End Parsing
Dominik Kempa (Johns Hopkins University); Barna Saha (UC Berkeley)

Average Sensitivity of Dynamic Programming
Soh Kumabe (The University of Tokyo); Yuichi Yoshida (National Institute of Informatics)

Enumerating k-SAT functions
Dingding Dong (Harvard); Nitya Mani and Yufei Zhao (MIT)

Collapsing the Tower - On the Complexity of Multistage Stochastic IPs
Kim-Manuel Klein and Janina Reuter (Kiel University)

Optimal angle bounds for Steiner triangulations of polygons
Christopher Bishop (Stony Brook University)

Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
Manuel Cáceres and Massimo Cairo (University of Helsinki); Brendan Mumey (Montana State University); Romeo Rizzi (University of Verona); Alexandru I. Tomescu (University of Helsinki)

A lower bound for the $n$-queens problem
Michael Simkin (Harvard University); Zur Luria (Azrieli College of Engineering)

Preprocessing Imprecise Points for the Pareto Front
Ivor van der Hoog (Utrecht University); Irina Kostitsyna (Technical University Eindhoven); Maarten Löffler (Utrecht University); Bettina Speckmann (Technical University Eindhoven)

A Sublinear Bound on the Page Number of Upward Planar Graphs
Paul Jungeblut, Laura Merker, and Torsten Ueckerdt (Karlsruhe Institute of Technology)

An Improved Analysis of Greedy for Online Steiner Forest
Etienne Bamas, Marina Drygala, and Andreas Maggiori (EPFL)

Constructing Many Faces in Arrangements of Lines and Segments
Haitao Wang (Utah State University)

Spectral recovery of binary censored block models
Souvik Dhara (Massachusetts Institute of Technology); Julia Gaudio (Northwestern University); Elchanan Mossel and Colin Sandon (Massachusetts Institute of Technology)

Deterministic Budget-Feasible Clock Auctions
Eric Balkanski and Pranav Garimidi (Columbia University); Vasilis Gkatzelis, Daniel Schoepflin, and Xizhi Tan (Drexel University)

Approximating Sumset Size
Anindya De (University of Pennsylvania); Shivam Nadimpalli and Rocco A. Servedio (Columbia University)

Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr\'echet Distance
Karl Bringmann (Saarland University and Max-Planck-Institute for Informatics); Anne Driemel (Hausdorff Center for Mathematics, University of Bonn); André Nusser (Max Planck Institute for Informatics); Ioannis Psarros (Hausdorff Center for Mathematics, University of Bonn)

Computing Lewis Weights to High Precision
Maryam Fazel (University of Washington); Yin Tat Lee (University Washington); Swati Padmanabhan (University of Washington); Aaron Sidford (Stanford University)

Distributed Zero-Knowledge Proofs Over Networks
Aviv Bick (Tel-Aviv University); Gillat Kol (Princeton University); Rotem Oshman (Tel-Aviv University)

Nearly $2$-Approximate Distance Oracles in Subquadratic Time
Shiri Chechik (Tel-Aviv University); Tianyi Zhang (Tsinghua University)

The popular assignment problem: when cardinality is more important than popularity
Tellikepalli Kavitha (Tata Institute of Fundamental Research); Tamás Király (Eotvos Lorand University); Jannik Matuschke (KU Leuven); Ildikó Schlotter (Centre for Economic and Regional Studies); Ulrike Schmidt-Kraepelin (Technische Universität Berlin)

Distortion-Oblivious Algorithms for Minimizing Flow Time
Yossi Azar (Tel Aviv University); Stefano Leonardi (University of Rome La Sapienza); Noam Touitou (Tel Aviv University)

A 3-Approximation Algorithm for Maximum Independent Set of Rectangles
Waldo Galvez (Technical University of Munich); Arindam Khan (Indian Institute of Science, Bengaluru, India); Mathieu Mari (University of Warsaw, Poland); Tobias Mömke (University of Augsburg); Madhusudhan Reddy Pittu (Indian Institute of Technology, Kharagpur, India); Andreas Wiese (Universidad de Chile)

Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
Jugal Garg (University of Illinois at Urbana-Champaign); Yixin Tao and László A. Végh (London School of Economics and Political Science)

Tight running times for minimum $\ell_q$-norm load balancing: beyond exponential dependencies on $1/\epsilon$
Lin Chen (Texas Tech University); Liangde Tao (Zhejiang University); José Verschae (Pontificia Universidad Católica de Chile)

On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
Kim-Manuel Klein (University of Kiel)

Markov Game with Switching Costs
Jian Li (Tsinghua University); Daogao Liu (University of Washington)

An Improved Local Search Algorithm for k-Median
Vincent Cohen-Addad (Google Research, Zurich); Anupam Gupta (Carnegie Mellon University, Pittsburgh PA 15217); Lunjia Hu (Stanford University); Hoon Oh (Carnegie Mellon University, Pittsburgh PA 15217); David Saulpic (Sorbonne Université, Paris)

Optimal Oblivious Parallel RAM
Gilad Asharov (Bar-Ilan University); Ilan Komargodski (Hebrew University and NTT Research); Wei-Kai Lin (Cornell University); Enoch Peserico (Universit`a degli Studi di Padova); Elaine Shi (CMU)

Fixed-Price Approximations in Bilateral Trade
Zi Yang Kang, Francisco Pernice, and Jan Vondrak (Stanford)

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
Akanksha Agrawal (IIT Madras); Lawqueen Kanesh (NUS Singapore); Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (IIT Hyderabad); M. S. Ramanujan (University of Warwick); Saket Saurabh (IMSc); Meirav Zehavi (Ben-Gurion University)

Directed tangle tree-decompositions and applications
Archontia C. Giannopoulou (Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Athens, Greece); Ken-ichi Kawarabayashi (National Institute of Informatics, Tokyo); Stephan Kreutzer (TU Berlin); O-joung Kwon (Incheon National University)

Faster Algorithms for Bounded-Difference Min-Plus Product
Shucheng Chi, Ran Duan, and Tianle Xie (Tsinghua University)

Unsplittable Flow on a Path: The Game!
Fabrizio Grandoni (IDSIA); Tobias Mömke (University of Augsburg); Andreas Wiese (Universidad de Chile)

Algorithmic Extensions of Dirac's Theorem
Fedor V. Fomin (Department of Informatics, University of Bergen, Norway.); Petr Golovach (University of Bergen, Norway); Danil Sagunov (St. Petersburg Department of Steklov's Institute); Kirill Simonov (TU Wien)

Streaming Regular Expression Membership and Pattern Matching
Bartłomiej Dudek and Paweł Gawrychowski (University of Wrocław); Garance Gourdel (DI/ENS, PSL Research University, IRISA Inria Rennes); Tatiana Starikovskaya (DI/ENS, PSL Research University)

Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
Shant Boodaghians (University of Illinois Urbana-Champaign); Bhaskar Ray Chaudhury (Max Planck Institute for Informatics); Ruta Mehta (University of Illinois Urbana-Champaign)

Sensitivity Oracles for All-Pairs Mincuts
Surender Baswana and Abhyuday Pandey (Indian Institute of Technology Kanpur)

How many Clusters ? - An algorithmic answer
Chiranjib Bhattacharyya (Department of Computer Science and Automation, Indian Institute of Science); Ravi Kannan (Microsoft Research); Amit Kumar (IIT Delhi)

Partially Optimal Edge Fault-Tolerant Spanners
Greg Bodwin (University of Michigan); Michael Dinitz (Johns Hopkins University); Caleb Robelle (MIT)

Approximate Hypergraph Vertex Cover and generalized Tuza’s conjecture
Venkatesan Guruswami (CMU); Sai Sandeep (Carnegie Mellon University)

On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies (University of Washington); Janardhan Kulkarni (Microsoft Research); Thomas Rothvoss (University of Washington); Sai Sandeep (Carnegie Mellon University); Jakub Tarnawski (Microsoft Research); Yihao Zhang (University of Washington)

Frequency Estimation with One-Sided Error
Piotr Indyk and Shyam Narayanan (Massachusetts Institute of Technology); David P. Woodruff (Carnegie Mellon University)

Online Weighted Matching with a Sample
Haim Kaplan (Tel Aviv University); David Naori and Danny Raz (Technion)

Optimal Sorting Circuits for Short Keys
Wei-Kai Lin (Cornell University); Elaine Shi (CMU)

Subexponential Parameterized Algorithms on Disk Graphs
Daniel Lokshtanov (University of California Santa Barbara, USA); Fahad Panolan (IIT Hyderabad, India); Saket Saurabh (IMSc); Jie Xue (University of California, Santa Barbara); Meirav Zehavi (Ben-Gurion University of the Negev)

Robust Load Balancing with Machine Learned Advice
Binghui Peng (Columbia University); Sara Ahmadian (Google Research); Hossein Esfandiari (Google); Vahab Mirrokni (Google Research)

Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack
Jiashuo Jiang (NYU Stern School of Business); Will Ma (Columbia Business School); Jiawei Zhang (NYU Stern School of Business)

Splay trees on trees
Benjamin Aram Berendsohn and László Kozma (Freie Universität Berlin)

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, and Ryan Williams (MIT); Hongxun Wu (Tsinghua University)

Simulating a stack using queues
Haim Kaplan (Tel Aviv University); Robert Tarjan (Princeton University); Or Zamir (Institute for Advanced Study); Uri Zwick (Tel Aviv University)

Limits of Preprocessing for Single-Server PIR
Giuseppe Persiano (Universita' di Salerno); Kevin Yeo (Google and Columbia University)

Robust Secretary and Prophet Algorithms for Packing Integer Programs
C.J. Argue (Carnegie Mellon University); Anupam Gupta (Carnegie Mellon); Marco Molinaro (PUC-Rio); Sahil Singla (Princeton University)

On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
Antonio Blanca (Pennsylvania State University); Pietro Caputo (University of Roma Tre); Zongchen Chen (Georgia Institute of Technology); Daniel Parisi (University of Roma Tre); Daniel Štefankovič (University of Rochester); Eric Vigoda (University of California, Santa Barbara)

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
Zongchen Chen (Georgia Institute of Technology); Andreas Galanis (University of Oxford); Daniel Štefankovič (University of Rochester); Eric Vigoda (University of California, Santa Barbara)

Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
Chandra Chekuri (University of Illinois at Urbana-Champaign); Kent Quanrud (Purdue University); Manuel R. Torres (University of Illinois at Urbana-Champaign)

Almost Tight Approximation Algorithms for Explainable Clustering
Hossein Esfandiari and Vahab Mirrokni (Google Research); Shyam Narayanan (Massachusetts Institute of Technology)

Online Discrepancy with Recourse for Vectors and Graphs
Anupam Gupta (Carnegie Mellon); Vijaykrishna Gurunathan (Indian Institute of Technology Bombay); Ravishankar Krishnaswamy (Microsoft Research); Amit Kumar (IIT Delhi); Sahil Singla (Princeton University)

Nested Dissection Meets IPMs : Planar Min-Cost Flow in Nearly-Linear Time
Sally Dong (University of Washington); Yu Gao (Georgia Institute of Technology); Gramoz Goranci (University of Glasgow); Yin Tat Lee (University Washington); Richard Peng (Georgia Tech & University of Waterloo); Sushant Sachdeva (University of Toronto); Guanghao Ye (University of Washington)

Polynomial Integrality Gap of Flow LP for Directed Steiner Tree
Bundit Laekhanukit (Shanghai University of Finance and Economics); Shi Li (University at Buffalo)

Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
Antares Chen (University of Chicago); Jonathan Shi and Luca Trevisan (Bocconi University)

Monotone edge flips to an orientation of maximum edge-connectivity \`a la Nash-Williams
Takehiro Ito (Tohoku University); Yuni Iwamasa (Kyoto University); Naonori Kakimura (Keio University); Naoyuki Kamiyama (Kyushu University); Yusuke Kobayashi (Kyoto University); Shun-ichi Maezawa (The University of Electro-Communications,); Yuta Nozaki (Hiroshima University); Yoshio Okamoto (The University of Electro-Communications,); Kenta Ozeki (Yokohama National University)

Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Peilin Zhong (Google Research)

Greedy Spanners in Euclidean Spaces Admit Sublinear Separators
Hung Le and Cuong Than (University of Massachusetts at Amherst)

Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
Alessandro Epasto, Mohammad Mahdian, Vahab Mirrokni, and Peilin Zhong (Google Research)

Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance
Joachim Gudmundsson and Sampson Wong (The University of Sydney)

Dynamic Geometric Set Cover, Revisited
Timothy M. Chan and Qizheng He (University of Illinois at Urbana-Champaign); Subhash Suri and Jie Xue (University of California at Santa Barbara)

Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
Timothy M. Chan and Da Wei Zheng (University of Illinois at Urbana-Champaign)

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs
Sayan Bandyapadhyay and William Lochet (University of Bergen); Daniel Lokshtanov (University of California, Santa Barbara); Saket Saurabh (IMSc); Jie Xue (University of California, Santa Barbara)

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Mitali Bafna (Harvard University); Max Hopkins (UCSD); Tali Kaufman (Bar Ilan University); Shachar Lovett (UCSD)

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the $\sqrt{n}$ Barrier
Shimon Kogan and Merav Parter (Weizmann IS)

A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
Joachim Gudmundsson and Martin P. Seybold (University of Sydney)

Perfect Matching in Random Graphs is as Hard as Tseitin
Per Austrin and Kilian Risse (School of Computer Science and Communication, KTH Royal Institute of Technology)

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Dániel Marx (CISPA Helmholtz Center for Information Security); Pranabendu Misra (Chennai Mathematical Institute); Daniel Neuen and Prafullkumar Tale (CISPA Helmholtz Center for Information Security)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
Daniel Neuen (CISPA Helmholtz Center for Information Security)

Fast Consensus via the Unconstrained Undecided State Dynamics
Gregor Bankhamer (University of Salzburg); Petra Berenbrink and Felix Biermeier (Universität Hamburg); Robert Elsässer (University of Salzburg); Hamed Hosseinpour, Dominik Kaaser, and Peter Kling (Universität Hamburg)

Online Graph Algorithms with Predictions
Yossi Azar (Tel Aviv University); Debmalya Panigrahi (Duke University); Noam Touitou (Tel Aviv University)

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

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
Soheil Behnezhad (University of Maryland); Sanjeev Khanna (University of Pennsylvania)

Better Sum Estimation via Weighted Sampling
Jakub Tětek and Lorenzo Beretta (University of Copenhagen)

Stochastic Vertex Cover with Few Queries
Soheil Behnezhad (University of Maryland); Avrim Blum (Toyota Technological Institute at Chicago); Mahsa Derakhshan (University of Maryland)

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing
Gramoz Goranci (University of Glasgow); Bernhard Haeupler (ETH Zurich and Carnegie Mellon University); Xiaorui Sun and Mingquan Ye (University of Illinois at Chicago); Goran Zuzic (ETH Zurich)

Approximately counting independent sets in bipartite graphs via graph containers
Matthew Jenssen (University of Birmingham); Will Perkins and Aditya Potukuchi (University of Illinois at Chicago)

Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
Adam Karczmarz (University of Warsaw)

Low Rank Approximation with Sparse Factors
David P. Woodruff and Taisuke Yasuda (Carnegie Mellon University)

Untangling Planar Graphs and Curves by Staying Positive
Santiago Aranguri (Department of Mathematics, Stanford University); Hsien-Chih Chang and Dylan Fridman (Department of Computer Science, Dartmouth College)

Algorithmic trade-offs for girth approximation in undirected graphs
Avi Kadaria and Liam Roditty (Bar-Ilan University); Aaron Sidford (Stanford University); Virginia Vassilevska Williams (MIT); Uri Zwick (Tel Aviv University)

Planar Multiway Cut with Terminals On Few Faces
Sukanya Pandey and Erik Jan van Leeuwen (Utrecht University)

Congruency-Constrained TU Problems Beyond the Bimodular Case
Martin Nägele, Richard Santiago, and Rico Zenklusen (ETH Zurich)

Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Nadiia Chepurko (MIT); Ken Clarkson (IBM Research); Praneeth Kacham and David P. Woodruff (Carnegie Mellon University)

Competitive Algorithms for Symmetric Rendezvous on the Line
Max Klimm, Guillaume Sagnol, Martin Skutella, and Khai Van Tran (TU Berlin)

Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Algorithm via Offline Dynamic Rectangle Union
Marvin Künnemann (ETH Zürich); André Nusser (Max Planck Institute for Informatics)

Augmenting Edge Connectivity via Isolating Cuts
Ruoxu Cen (Duke University); Jason Li (Carnegie Mellon University); Debmalya Panigrahi (Duke University)

Single Sample Prophet Inequalities via Greedy-Ordered Selection
Constantine Caramanis (The University of Texas at Austin); Paul Duetting (Google Research); Matthew Faw (The University of Texas at Austin); Federico Fusco and Philip Lazos (Sapienza University of Rome); Stefano Leonardi (University of Rome La Sapienza); Orestis Papadigenopoulos (The University of Texas at Austin); Emmanouil Pountourakis (Drexel University); Rebecca Reiffenhauser (Sapienza University of Rome)

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Karl Bringmann, Nick Fischer, and Vasileios Nakos (Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany)

Scalar and Matrix Chernoff Bounds from $\ell_{\infty}$-Independence
Tali Kaufman (Department of Computer Science, Bar-Ilan University); Rasmus Kyng and Federico Soldà (Department of Computer Science, ETH Zurich)

Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
Amir Abboud and Robert Krauthgamer (Weizmann Institute of Science); Ohad Trabelsi (University of Michigan)

Testing matrix product states
Mehdi Soleimanifar (MIT); John Wright (UT Austin)

Learning-Augmented Weighted Paging
Nikhil Bansal (CWI Amsterdam and TU Eindhoven); Christian Coester (CWI Amsterdam); Ravi Kumar, Manish Purohit, and Erik Vee (Google)

Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology
Amir Nayyeri, Mitchell Black, William Maxwell, and Eli Winkelman (Oregon State University)

Local Search for Weighted Tree Augmentation and Steiner Tree
Vera Traub and Rico Zenklusen (ETH Zurich)

Promise Constraint Satisfaction and Width
Albert Atserias (Universitat Politècnica de Catalunya); Victor Dalmau (Universitat Pompeu Fabra)

An Improved Algorithm for The $k$-Dyck Edit Distance Problem
Dvir Fried (Bar Ilan University); Shay Golan (Bar-Ilan University); Tomasz Kociumaka (UC Berkeley); Tsvi Kopelowitz and Ely Porat (Bar Ilan University); Tatiana Starikovskaya (Ecole Normale Superieure)

Compact Redistricting Plans Have Many Spanning Trees
Ariel Procaccia and Jamie Tucker-Foltz (Harvard University)

Approximating The Arboricity in Sublinear Time
Talya Eden (MIT); Dana Ron (Tel Aviv University); Saleet Mossel (MIT)

Strong recovery of geometric planted matchings
Dmitriy Kunisky and Jonathan Niles-Weed (New York University)

A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision
Sumanta Ghosh, Rohit Gurjar, and Roshan Raj (IIT Bombay)

The complexity of testing all properties of planar graphs, and the role of isomorphism
Sabyasachi Basu (University of California, Santa Cruz); Akash Kumar (EPFL); C. Seshadhri (University of California, Santa Cruz)

Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k
Calvin Beideman, Karthekeyan Chandrasekaran, and Weihang Wang (University of Illinois at Urbana-Champaign)

Selectable Heaps and Optimal Lazy Search Trees
Bryce Sandlund and Lingyi Zhang (University of Waterloo)

Distribution-free Testing for Halfspaces Requires PAC Learning
Xi Chen and Shyamal Patel (Columbia University)

Twin-width VI: the lens of contraction sequences
Édouard Bonnet (LIP, ENS Lyon); Eun Jung Kim (LAMSADE, Paris-Dauphine University); Amadeus Reinald and Stéphan Thomassé (LIP, ENS Lyon)

Algorithmic Thresholds for Refuting Random Polynomial Systems
Jun-Ting Hsieh and Pravesh K. Kothari (Carnegie Mellon University)

Simulating Random Walks in Random Streams
John Kallaugher (The University of Texas at Austin); Michael Kapralov (EPFL); Eric Price (The University of Texas at Austin)

A Two Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching
Sepehr Assadi (Rutgers University)

Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Kevin Lu (Citadel Securities); Virginia Vassilevska Williams, Nicole Wein, and Zixuan Xu (MIT)

Algorithms Using Local Graph Features to Predict Epidemics
Yeganeh Alimohammadi (Stanford University); Christian Borgs (University of California Berkeley); Amin Saberi (Stanford University)

Metric Distortion Bounds for Randomized Social Choice
Moses Charikar and Prasanna Ramakrishnan (Stanford University)

Combinatorial Gap Theorem and Reductions between Promise CSPs
Libor Barto (Charles University); Marcin Kozik (Theoretical Computer Science, Faculty of Mathematics and Camputer Science, Jagiellonian University)

Balanced Allocations: Caching and Packing, Thinning and Twinning
Dimitrios Los and Thomas Sauerwald (University of Cambridge); John Sylvester (University of Glasgow)

Approximating Fair Clustering with Cascaded Norm Objectives
Eden Chlamtáč (Ben Gurion University); Yury Makarychev and Ali Vakilian (TTIC)

How Compression and Approximation Affect Efficiency in String Distance Measures
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, and Barna Saha (UC Berkeley)

Recognizing k-leaf powers in polynomial time, for constant k
Manuel Lafond (University of Sherbrooke)

Near-Optimal Spanners for General Graphs in Linear Time
Hung Le (University of Massachusetts); Shay Solomon (Tel Aviv University)