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)