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)