**Concentration on the Boolean hypercube via pathwise stochastic analysis**

Ronen Eldan (*Weizmann Institute of Science*), Renan Gross (*Weizmann Institute of Science*)

**Explicit near-Ramanujan graphs of every degree**

Sidhanth Mohanty (*University of California Berkeley*), Ryan O'Donnell (*Carnegie Mellon University*), Pedro Paredes (*Carnegie Mellon University*)

**QCSP monsters and the demise of the Chen Conjecture**

Dmitriy Zhuk (*Lomonosov Moscow State University*), Barnaby Martin (*Durham University*)

**An improved approximation algorithm for ATSP**

Vera Traub (*University of Bonn*), Jens Vygen (*University of Bonn*)

**Improved bounds for the sunflower lemma**

Ryan Alweiss (*Princeton University*), Shachar Lovett (*UCSD*), Kewen Wu (*Peking University*), Jiapeng Zhang (*Harvard University*)

**Three-in-a-tree in near linear time**

Kai-Yuan Lai (*National Taiwan University*), Hsueh-I Lu (*National Taiwan University*), Mikkel Thorup (*University of Copenhagen*)

**New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs**

Maximilian Probst (*Department of Computer Science, University of Copenhagen*), Virginia Vassilevska Williams (*Massachusetts Institute of Technology*), Nicole Wein (*MIT*)

**How to lose at Monte Carlo: a simple dynamical system whose typical statistical behavior is non computable.**

Cristobal Rojas (*Departamento de Matemáticas, Universidad Andres Bello, Chile.*), Michael Yampolsky (*Department of Mathematics, University of Toronto, Canada.*)

**Approximately Stable Committee Selection**

Zhihao Jiang (*Tsinghua University*), Kamesh Munagala (*Duke University*), Kangning Wang (*Duke University*)

**Testing noisy linear functions for sparsity**

Xue Chen (*Northwestern University*), Anindya De (*University of Pennsylvania*), Rocco A. Servedio (*Columbia University*)

**Dynamic Algorithms for LIS and Distance to Monotonicity**

Michael Mitzenmacher (*Harvard University*), Saeed Seddighin (*Harvard University*)

**Decision list compression by mild random restrictions**

Shachar Lovett (*UCSD*), Kewen Wu (*Peking University*), Jiapeng Zhang (*Harvard University*)

**XOR Lemmas for Resilient Functions Against Polynomials**

Eshan Chattopadhyay (*Cornell University*), Pooya Hatami (*Ohio State University*), Kaave Hosseini (*Carnegie Mellon University*), Shachar Lovett (*UCSD*), David Zuckerman (*University of Texas at Austin*)

**Bare quantum simultaneity versus classical interactivity in communication complexity**

Dmitry Gavinsky (*Institute of Mathematics of the Czech Academy of Sciences*)

**Improved bounds for perfect sampling of $k$-colorings in graphs**

Siddharth Bhandari (*Tata Institute of Fundamental Research, Mumbai*), Sayantan Chakraborty (*Tata Institute of Fundamental Research, Mumbai*)

**Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?**

Yaroslav Alekseev (*Steklov Institute of Mathematics at St. Petersburg, and Chebyshev Laboratory at St. Petersburg State University*), Dima Grigoriev (*CNRS, Mathematiques, Universite de Lille*), Edward A. Hirsch (*Steklov Institute of Mathematics at St. Petersburg*), Iddo Tzameret (*Royal Holloway, University of London*)

**No-Signaling Proofs with $O(\sqrt{\log n})$ Provers is in PSPACE**

Dhiraj Holden (*MIT*), Yael Tauman Kalai (*Microsoft Research*)

**Faster Energy Maximization for Faster Maximum Flow**

Yang P. Liu (*Stanford University*), Aaron Sidford (*Stanford University*)

**Automating Cutting Planes is NP-Hard**

Mika Goos (*Stanford University*), Sajin Koroth (*Simon Fraser University*), Ian Mertz (*University of Toronto*), Toniann Pitassi (*University of Toronto and IAS*)

**Fully-dynamic Planarity Testing in Polylogarithmic Time**

Jacob Holm (*University of Copenhagen*), Eva Rotenberg (*Technical University of Denmark*)

**An Exponential Time Parameterized Algorithm for Planar Disjoint Paths**

Daniel Lokshtanov (*University of California Santa Barbara, USA*), Pranabendu Misra (*Max Planck Institute for Informatics, Saarbrucken, Germany*), Michał Pilipczuk (*University of Warsaw, Poland*), Saket Saurabh (*Institute of Mathematical Sciences, Chennai, India*), Meirav Zehavi (*Ben-Gurion University, Beersheba, Israel*)

**Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions**

Shuichi Hirahara (*National Institute of Informatics*)

**Quadratic speedup for finding marked vertices by quantum walks**

Andris Ambainis (*University of Latvia*), Andras Gilyen (*IQIM, Caltech*), Stacey Jeffery (*CWI*), Martins Kokainis (*University of Latvia*)

**Distance Sensitivity Oracles With Subcubic Preprocessing Time and Fast Query Time**

Sarel Cohen (*Tel-Aviv University*), Shiri Chechik (*Tel-Aviv University*)

**AND Testing and Robust Judgement Aggregation**

Yuval Filmus (*Technion*), Noam Lifshitz (*Hebrew University*), Dor Minzer (*Institute of Advanced Study*), Elchanan Mossel (*MIT*)

**Fast sampling and counting k-SAT solutions in the local lemma regime**

Weiming Feng (*Nanjing University*), Heng Guo (*University of Edinburgh*), Yitong Yin (*Nanjing University*), Chihao Zhang (*Shanghai Jiao Tong University*)

**Reducing Path TSP to TSP**

Vera Traub (*University of Bonn*), Jens Vygen (*University of Bonn*), Rico Zenklusen (*ETH Zurich*)

**Implementing geometric complexity theory: On the separation of orbit closures via symmetries**

Christian Ikenmeyer (*University of Liverpool*), Umangathan Kandasamy (*Saarland University*)

**Rounding Dynamic Matchings Against an Adaptive Adversary**

David Wajc (*Carnegie Mellon University*)

**Fast Hashing with Strong Concentration Bounds**

Anders Aamand (*University of Copenhagen*), Jakob Bæk Tejs Knudsen (*University of Copenhagen*), Mathias Bæk Tejs Knudsen (*SupWiz*), Peter Michael Reichstein Rasmussen (*University of Copenhagen*), Mikkel Thorup (*University of Copenhagen*)

**Lower Bound for Succinct Range Minimum Query**

Mingmou Liu (*Nanjing University*), Huacheng Yu (*Princeton University*)

**Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time**

Jesper Nederlof (*Utrecht University*)

**Optimally Resilient Codes for List-Decoding from Insertions and Deletions**

Venkatesan Guruswami (*Carnegie Mellon University*), Bernhard Haeupler (*Carnegie Mellon University*), Amirbehshad Shahrasbi (*Carnegie Mellon University*)

**The program-size complexity of self-assembled paths**

Pierre-Étienne Meunier (*Hamilton Institute, Maynooth University*), Damien Regnault (*IBISC, Université Évry, Université Paris-Saclay*), Damien Woods (*Hamilton Institute, Maynooth University*)

**Bipartite TSP in $O(1.9999^n)$ Time, Assuming Quadratic Time Matrix Multiplication**

Jesper Nederlof (*Utrecht University*)

**Towards a Better Understanding of Randomized Greedy Matching**

Zhihao Gavin Tang (*Shanghai University of Finance and Economics*), Xiaowei Wu (*University of Vienna*), Yuhao Zhang (*The University of Hong Kong*)

**Approximating Text-to-Pattern Hamming Distances**

Timothy M. Chan (*UIUC*), Shay Golan (*Bar-Ilan University*), Tomasz Kociumaka (*Bar-Ilan University*), Tsvi Kopelowitz (*Bar-Ilan University*), Ely Porat (*Bar Ilan University*)

**Separating the Communication Complexity of Truthful and Non-Truthful Combinatorial Auctions**

Sepehr Assadi (*Rutgers University*), Hrishikesh Khandeparkar (*Princeton University*), Raghuvansh Saxena (*Princeton University*), S. Matthew Weinberg (*Princeton University*)

**Faster Parallel Algorithm for Approximate Shortest Path**

Jason Li (*Carnegie Mellon University*)

**Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)**

Matthew Coudron (*IQC/University of Waterloo, University of Maryland/NIST*), Sanketh Menda (*University of Waterloo*)

**Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths**

Nairen Cao (*Georgetown University*), Jeremy Fineman (*Georgetown University*), Katina Russell (*Georgetown University*)

**Efficient sampling and counting algorithms for the Potts model on $\mathbb Z^d$ at all temperatures**

Christian Borgs (*Microsoft Research*), Jennifer Chayes (*Microsoft Research*), Tyler Helmuth (*University of Bristol*), Will Perkins (*University of Illinois at Chicago*), Prasad Tetali (*Georgia Institute of Technology*)

**Strong Self-Concordance and Sampling**

Aditi Laddha (*Georgia Tech*), Yin Tat Lee (*University Washington*), Santosh Vempala (*Georgia Tech*)

**An Improved Approximation Algorithm for TSP in the Half Integral Case**

Anna R. Karlin (*University of Washington*), Nathan Klein (*University of Washington*), Shayan Oveis Gharan (*University of Washington*)

**Nearly Optimal Static Las Vegas Succinct Dictionary**

Huacheng Yu (*Princeton University*)

**All non-trivial variants of 3-LDT are equivalent**

Bartłomiej Dudek (*University of Wrocław*), Paweł Gawrychowski (*University of Wrocław*), Tatiana Starikovskaya (*Ecole Normale Superieure*)

**The Impossibility of Efficient Quantum Weak Coin Flipping**

Carl A. Miller (*NIST, University of Maryland*)

**Caching with Time Windows**

Anupam Gupta (*Carnegie Mellon*), Amit Kumar (*IIT Delhi*), Debmalya Panigrahi (*Duke University*)

**Separations and Equivalences Between Turnstile Streaming and Linear Sketching**

John Kallaugher (*The University of Texas at Austin*), Eric Price (*The University of Texas at Austin*)

**Strong Average-Case Lower Bounds from Non-trivial Derandomization**

Lijie Chen (*Massachusetts Institute of Technology*), Hanlin Ren (*Tsinghua University*)

**Online Vector Balancing and Geometric Discrepancy**

Nikhil Bansal (*TU Eindhoven, and Centrum Wiskunde & Informatica*), Haotian Jiang (*Paul G. Allen School of CSE, University of Washington*), Sahil Singla (*Princeton University and Institute for Advanced Study*), Makrand Sinha (*CWI*)

**Fooling Gaussian PTFs via Local Hyperconcentration**

Ryan O'Donnell (*Carnegie Mellon University*), Rocco A. Servedio (*Columbia University*), Li-Yang Tan (*Stanford University*)

**Constant-factor approximation of near-linear edit distance in near-linear time**

Joshua Brakensiek (*Stanford University*), Aviad Rubinstein (*Stanford University*)

**Sharp Threshold Results for Computational Complexity**

Lijie Chen (*MIT*), Ce Jin (*Tsinghua University*), R. Ryan Williams (*MIT*)

**An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications**

Haotian Jiang (*University of Washington*), Yin Tat Lee (*University of Washington, Microsoft Research Redmond*), Zhao Song (*IAS, Princeton University*), Sam Wong (*Microsoft Research Redmond*)

**The Karger-Stein Algorithm is Optimal for k-cut**

Anupam Gupta (*Carnegie Mellon University*), Euiwoong Lee (*New York University*), Jason Li (*Carnegie Mellon University*)

**The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness**

Moran Feldman (*University of Haifa*), Ashkan Norouzi-Fard (*Google Research*), Ola Svensson (*EPFL*), Rico Zenklusen (*ETH Zurich*)

**A Lower Bound for Parallel Submodular Minimization**

Eric Balkanski (*Harvard University*), Yaron Singer (*Harvard University*)

**(Semi)Algebraic Proofs over $\{\pm 1\}$ Variables**

Dmitry Sokolov (*Lund University, University of Copenhagen*)

**Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds**

Rong Ge (*Duke University*), Holden Lee (*Duke University*), Jianfeng Lu (*Duke University*)

**Does Learning Require Memorization? A Short Tale about a Long Tail**

Vitaly Feldman (*Google Research*)

**On the Need for Large Quantum Depth**

Nai-Hui Chia (*University of Texas at Austin*), Kai-Min Chung (*Institute of Information Science, Academia Sinica*), Ching-Yi Lai (*Institute of Communications Engineering, National Chiao Tung University*)

**Entanglement subvolume law for 2D frustration-free spin systems**

Anurag Anshu (*University of Waterloo*), Itai Arad (*Technion*), David Gosset (*University of Waterloo*)

**Better Secret Sharing via Robust Conditional Disclosure of Secrets**

Benny Applebaum (*Tel-Aviv University*), Amos Beimel (*Ben-Gurion University of the Negev*), Oded Nir (*Tel-Aviv University*), Naty Peter (*Ben-Gurion University of the Negev*)

**Online Primal Dual Meets Online Matching with Stochastic Rewards: Configuration LP to the Rescue**

Zhiyi Huang (*The University of Hong Kong*), Qiankun Zhang (*The University of Hong Kong*)

**Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius**

Chong Shangguan (*Tel Aviv University*), Itzhak Tamo (*Tel Aviv University*)

**Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal**

Lingxiao Huang (*Yale University*), Nisheeth K. Vishnoi (*Yale University*)

**The Power of Factorization Mechanisms in Local and Central Differential Privacy**

Alexander Edmonds (*University of Toronto*), Aleksandar Nikolov (*University of Toronto*), Jonathan Ullman (*Northeastern University*)

**Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization**

Vaclav Rozhon (*ETH Zurich*), Mohsen Ghaffari (*ETH Zurich*)

**On the Nisan-Ronen conjecture for submodular valuations**

Giorgos Christodoulou (*University of Liverpool*), Elias Koutsoupias (*University of Oxford*), Annamaria Kovacs (*Goethe University Frankfurt*)

**Does Preprocessing help in Fast Sequence Comparisons?**

Elazar Goldenberg (*The Academic College of Tel Aviv-Yaffo*), Aviad Rubinstein (*Stanford University*), Barna Saha (*University of California Berkeley*)

**Breaching the 2-Approximation Barrier for Connectivity Augmentation: a Reduction to Steiner Tree**

Jaroslaw Byrka (*University of Wroclaw*), Fabrizio Grandoni (*IDSIA, Switzerland*), Afrouz Jabal Ameli (*IDSIA, Switzerland*)

**On the Computability of Continuous Maximum Entropy Distributions with Applications**

Jonathan Leake (*KTH*), Nisheeth K. Vishnoi (*Yale University*)

**Walking Randomly, Massively, and Efficiently**

Jakub Łącki (*Google Research, New York*), Slobodan Mitrović (*MIT*), Krzysztof Onak (*IBM Research*), Piotr Sankowski (*University of Warsaw, Poland*)

**One-shot Signatures and Applications to Hybrid Quantum/Classical Authentication**

Ryan Amos (*Princeton University*), Marios Georgiou (*City University of New York*), Aggelos Kiayias (*University of Edinburgh*), Mark Zhandry (*Princeton University*)

**Contention Resolution without Collision Detection**

Michael A. Bender (*Stony Brook University*), Tsvi Kopelowitz (*Bar-Ilan University*), William Kuszmaul (*MIT*), Seth Pettie (*University of Michigan*)

**Unbounded lower bound for k-server against weak adversaries**

Marcin Bienkowski (*University of Wroclaw*), Jarosław Byrka (*University of Wroclaw*), Christian Coester (*CWI*), Łukasz Jez (*University of Wroclaw*)

**Constant factor approximations to edit distance on far input pairs in nearly linear time**

Michal Koucky (*Charles University, Prague*), Michael Saks (*Rutgers Unviersity*)

**Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum**

Karl Bringmann (*Max-Planck-Institute for Informatics*), Vasileios Nakos (*National Technical University of Athens*)

**Solving Tall Dense Linear Programs in Nearly Linear Time**

Jan van den Brand (*KTH Royal Institute of Technology*), Yin Tat Lee (*Microsoft Research*), Aaron Sidford (*Stanford University*), Zhao Song (*IAS / Princeton*)

**New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut**

Amir Abboud (*IBM Almaden Research Center*), Vincent Cohen-Addad (*CNRS, UPMC*), Philip N Klein (*Brown University*)

**A polynomial lower bound on adaptive complexity of submodular maximization**

Wenzheng Li (*Stanford*), Paul Liu (*Stanford*), Jan Vondrak (*Stanford*)

**Optimal Time and Space Leader Election in Population Protocols**

Petra Berenbrink (*University of Hamburg*), George Giakkoupis (*INRIA*), Peter Kling (*University of Hamburg*)

**A Spectral Approach to Network Design**

Lap Chi Lau (*University of Waterloo*), Hong Zhou (*University of Waterloo*)

**Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning**

Nai-Hui Chia (*University of Texas at Austin*), Andras Gilyen (*IQIM, Caltech*), Tongyang Li (*University of Maryland*), Han-Hsuan Lin (*University of Texas at Austin*), Ewin Tang (*University of Washington*), Chunhao Wang (*University of Texas at Austin*)

**Interaction is necessary for distributed learning with privacy or communication constraints**

Yuval Dagan (*MIT*), Vitaly Feldman (*Google Research*)

**Catalytic Approaches to the Tree Evaluation Problem**

Ian Mertz (*University of Toronto*), James Cook (*University of Toronto*)

**Improved Analysis of Higher Order Random Walks and Applications**

Vedat Levi Alev (*University of Waterloo*), Lap Chi Lau (*University of Waterloo*)

**Hitting Topological Minors is FPT**

Fedor V. Fomin (*Department of Informatics, University of Bergen, Norway.*), Daniel Lokshtanov (*University of California Santa Barbara, USA*), Fahad Panolan (*Department of Computer Science and Engineering, IIT Hyderabad, India*), Saket Saurabh (*IMSc*), Meirav Zehavi (*Ben-Gurion University*)

**Lifting Sum-of-Squares Lower Bounds: Degree-2 to Degree-4**

Sidhanth Mohanty (*University of California Berkeley*), Prasad Raghavendra (*University of California Berkeley*), Jeff Xu (*University of California Berkeley*)

**Interactive Error Resilience Beyond $\frac{2}{7}$**

Klim Efremenko (*Ben-Gurion University*), Gillat Kol (*Princeton University*), Raghuvansh R. Saxena (*Princeton University*)

**Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators**

Alexandr Andoni (*Columbia University*), Clifford Stein (*Columbia University*), Peilin Zhong (*Columbia University*)

**Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems**

Aram Harrow (*MIT*), Saeed Mehraban (*Caltech*), Mehdi Soleimanifar (*MIT*)

**Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity**

Venkatesan Guruswami (*Carnegie Mellon University*), Andrii Riazanov (*Carnegie Mellon University*), Min Ye (*Tsinghua-Berkeley Shenzhen Institute*)

**Post-Quantum Zero Knowledge in Constant Rounds**

Omri Shmueli (*Tel Aviv University*), Nir Bitansky (*Tel Aviv University*)

**Smoothed complexity of local Max-Cut and binary Max-CSP**

Emmanouil-Vasileios Vlatakis-Gkaragkounis (*Columbia University*), Xi Chen (*Columbia University*), Chenghao Guo (*IIIS, Tsinghua University*), Mihalis Yannakakis (*Columbia University*), Xinzhi Zhang (*IIIS, Tsinghua University*)

**A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix**

Daniel Dadush (*Centrum Wiskunde & Informatica, Amsterdam*), Sophie Huiberts (*Centrum Wiskunde & Informatica, Amsterdam*), Bento Natura (*London School of Economics and Political Science*), László A. Végh (*London School of Economics and Political Science*)

**Near-Optimal Fully Dynamic Densest Subgraph**

Saurabh Sawlani (*Georgia Institute of Technology*), Junxing Wang (*Carnegie Mellon University*)

**A Robust Version of Hegedus's Lemma, with Applications**

Srikanth Srinivasan (*Department of Mathematics, IIT Bombay*)

**Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond**

Yeshwanth Cherapanamjeri (*UC Berkeley*), Sam Hopkins (*UC Berkeley*), Tarun Kathuria (*UC Berkeley*), Prasad Raghavendra (*UC Berkeley*), Nilesh Tripuraneni (*UC Berkeley*)

**Constant Girth Approximation for Directed Graphs in Subquadratic Time**

Shiri Chechik (*Tel-Aviv University*), Yang P. Liu (*Stanford University*), Omer Rotem (*Tel-Aviv University*), Aaron Sidford (*Stanford University*)

**Non-Adaptive Adaptive Sampling on Turnstile Streams**

Sepideh Mahabadi (*TTIC*), Ilya Razenshteyn (*Microsoft Research*), David P. Woodruff (*Carnegie Mellon University*), Samson Zhou (*Carnegie Mellon University*)

**Interactive shallow Clifford circuits: quantum advantage against NC$^1$ and beyond**

Daniel Grier (*University of Waterloo*), Luke Schaeffer (*University of Waterloo*)

**Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments**

Sitan Chen (*MIT*), Jerry Li (*Microsoft Research*), Zhao Song (*UT Austin*)

**Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms**

Sagnik Mukhopadhyay (*KTH Royal Institute of Technology*), Danupon Nanongkai (*KTH Royal Institute of Technology*)

**Private Stochastic Convex Optimization: Optimal Rates in Linear Time**

Vitaly Feldman (*Google Research*), Tomer Koren (*Google Research*), Kunal Talwar (*Google Research*)

**A Phase Transition and Quadratic Time Estimator for Network Reliability**

David Karger (*MIT*)

**Efficiently Learning Structured Distributions from Untrusted Batches**

Sitan Chen (*MIT*), Jerry Li (*Microsoft Research*), Ankur Moitra (*Math & CSAIL, MIT*)

**Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent**

Arun Jambulapati (*Stanford University*), Yin Tat Lee (*University Washington*), Jerry Li (*Microsoft Research*), Swati Padmanabhan (*University of Washington*), Kevin Tian (*Stanford University*)

**Extractors for Adversarial Sources via Extremal Hypergraphs**

Eshan Chattopadhyay (*Cornell University*), Jesse Goodman (*Cornell University*), Vipul Goyal (*Carnegie Melon University*), Xin Li (*Johns Hopkins University*)

**Stochastic Matching with Few Queries: $(1-\varepsilon)$ Approximation**

Soheil Behnezhad (*University of Maryland*), Mahsa Derakhshan (*University of Maryland*), MohammadTaghi Hajiaghayi (*University of Maryland*)

**Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits**

Sepehr Assadi (*Rutgers University*), Chen Wang (*Rutgers University*)

**Data Structures Meet Cryptography: 3SUM with Preprocessing**

Alexander Golovnev (*Harvard University*), Siyao Guo (*NYU Shanghai*), Thibaut Horel (*MIT*), Sunoo Park (*MIT & Harvard*), Vinod Vaikuntanathan (*MIT*)