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)