| 2022 | 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022 |
| 2021 | 2-norm Flow Diffusion in Near-Linear Time. Li Chen, Richard Peng, Di Wang |
| 2021 | A Better-Than-2 Approximation for Weighted Tree Augmentation. Vera Traub, Rico Zenklusen |
| 2021 | A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Wegrzycki |
| 2021 | A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows. Anupam Gupta, Amit Kumar, Debmalya Panigrahi |
| 2021 | A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan |
| 2021 | A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak |
| 2021 | A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna |
| 2021 | A Quantum Advantage for a Natural Streaming Problem. John Kallaugher |
| 2021 | A Single-Exponential Time 2-Approximation Algorithm for Treewidth. Tuukka Korhonen |
| 2021 | A Theory of PAC Learnability of Partial Concept Classes. Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran |
| 2021 | A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. Wenzheng Li, Jan Vondrák |
| 2021 | A direct product theorem for quantum communication complexity with applications to device-independent QKD. Rahul Jain, Srijita Kundu |
| 2021 | A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects. Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus |
| 2021 | A time and space optimal stable population protocol solving exact majority. David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, Grzegorz Stachowiak |
| 2021 | APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
| 2021 | Affine Extractors for Almost Logarithmic Entropy. Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao |
| 2021 | Almost Optimal Inapproximability of Multidimensional Packing Problems. Sai Sandeep |
| 2021 | Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms. Robert Robere, Jeroen Zuiddam |
| 2021 | An Invariance Principle for the Multi-slice, with Applications. Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer |
| 2021 | Applications of Random Algebraic Constructions to Hardness of Approximation. Boris Bukh, Karthik C. S., Bhargav Narayanan |
| 2021 | Approximability of all finite CSPs with linear sketches. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy |
| 2021 | Approximating Maximum Independent Set for Rectangles in the Plane. Joseph S. B. Mitchell |
| 2021 | At most 3.55 Cory Palmer, Dömötör Pálvölgyi |
| 2021 | Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. Xiao Mao |
| 2021 | Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models. Enric Boix-Adserà, Guy Bresler, Frederic Koehler |
| 2021 | Combinatorial Contracts. Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim |
| 2021 | Constructive Separations and Their Consequences. Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams |
| 2021 | Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time. Neil Olver, Leon Sering, Laura Vargas Koch |
| 2021 | Covering Polygons is Even Harder. Mikkel Abrahamsen |
| 2021 | Demystifying the border of depth-3 algebraic circuits. Pranjal Dutta, Prateek Dwivedi, Nitin Saxena |
| 2021 | Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak |
| 2021 | Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. Mohsen Ghaffari, Fabian Kuhn |
| 2021 | Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut. Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
| 2021 | Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. Marco Bressan, Marc Roth |
| 2021 | Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu |
| 2021 | Exponential Separations Between Learning With and Without Quantum Memory. Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li |
| 2021 | FIXP-membership via Convex Optimization: Games, Cakes, and Markets. Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender |
| 2021 | FOCS 2021 Preface. Nisheeth K. Vishnoi |
| 2021 | Faster Sparse Minimum Cost Flow by Electrical Flow Localization. Kyriakos Axiotis, Aleksander Madry, Adrian Vladu |
| 2021 | Feature Purification: How Adversarial Training Performs Robust Deep Learning. Zeyuan Allen-Zhu, Yuanzhi Li |
| 2021 | Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR. Itai Dinur, Nathan Keller, Ohad Klein |
| 2021 | Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup |
| 2021 | Fooling Constant-Depth Threshold Circuits (Extended Abstract). Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell |
| 2021 | Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. Yu Gao, Yang P. Liu, Richard Peng |
| 2021 | Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract). Wenyu Jin, Xiaorui Sun |
| 2021 | Group isomorphism is nearly-linear time for most orders. Heiko Dietrich, James B. Wilson |
| 2021 | Hardness of Approximate Diameter: Now for Undirected Graphs. Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams |
| 2021 | Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. Lijie Chen, Roei Tell |
| 2021 | Harmonic Persistent Homology (extended abstract). Saugata Basu, Nathanael Cox |
| 2021 | Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. Vitaly Feldman, Audra McMillan, Kunal Talwar |
| 2021 | Hop-Constrained Metric Embeddings and their Applications. Arnold Filtser |
| 2021 | Improved Extractors for Small-Space Sources. Eshan Chattopadhyay, Jesse Goodman |
| 2021 | Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]. Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters |
| 2021 | Improved Online Correlated Selection. Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, Yan Zhong |
| 2021 | Integer programs with bounded subdeterminants and two nonzeros per row. Samuel Fiorini, Gwenaël Joret, Stefan Weltge, Yelena Yuditsky |
| 2021 | LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira |
| 2021 | Learning Deep ReLU Networks Is Fixed-Parameter Tractable. Sitan Chen, Adam R. Klivans, Raghu Meka |
| 2021 | Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering. Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul |
| 2021 | List-decodability with large radius for Reed-Solomon codes. Asaf Ferber, Matthew Kwan, Lisa Sauermann |
| 2021 | MAJORITY-3SAT (and Related Problems) in Polynomial Time. Shyan Akmal, Ryan Williams |
| 2021 | Minimum Cuts in Directed Graphs via Partial Sparsification. Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud |
| 2021 | Minor Sparsifiers and the Distributed Laplacian Paradigm. Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye |
| 2021 | Multiway Online Correlated Selection. Guy Blanc, Moses Charikar |
| 2021 | New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. Guillaume Moroz |
| 2021 | Noise and the Frontier of Quantum Supremacy. Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu |
| 2021 | Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Oded Goldreich, Avi Wigderson |
| 2021 | On Classifying Continuous Constraint Satisfaction problems. Tillmann Miltzow, Reinier F. Schmiermann |
| 2021 | On Worst-Case Learning in Relativized Heuristica. Shuichi Hirahara, Mikito Nanashima |
| 2021 | On statistical inference when fixed points of belief propagation are unstable. Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra |
| 2021 | On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round. Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa |
| 2021 | On the Nisan-Ronen conjecture. George Christodoulou, Elias Koutsoupias, Annamária Kovács |
| 2021 | On the Power of Preconditioning in Sparse Linear Regression. Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi |
| 2021 | One-step replica symmetry breaking of random regular NAE-SAT. Danny Nam, Allan Sly, Youngtak Sohn |
| 2021 | Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau |
| 2021 | Optimal Approximate Distance Oracle for Planar Graphs. Hung Le, Christian Wulff-Nilsen |
| 2021 | Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. Jasper C. H. Lee, Paul Valiant |
| 2021 | PPSZ is better than you think. Dominik Scheder |
| 2021 | Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, Céline M. F. Swennenhuis |
| 2021 | Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier. Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry |
| 2021 | Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron. Emmanuel Abbe, Shuangping Li, Allan Sly |
| 2021 | Properly learning decision trees in almost polynomial time. Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan |
| 2021 | Quantum learning algorithms imply circuit lower bounds. Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram |
| 2021 | Quantum soundness of testing tensor codes. Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen |
| 2021 | Quantum supremacy and hardness of estimating output probabilities of quantum circuits. Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh |
| 2021 | Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits. Nolan J. Coble, Matthew Coudron |
| 2021 | Random Order Online Set Cover is as Easy as Offline. Anupam Gupta, Gregory Kehne, Roie Levin |
| 2021 | Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes. Akash Kumar, C. Seshadhri, Andrew Stolman |
| 2021 | Rapid mixing of Glauber dynamics via spectral independence for all degrees. Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang |
| 2021 | Reachability in Vector Addition Systems is Ackermann-complete. Wojciech Czerwinski, Lukasz Orlikowski |
| 2021 | Robust recovery for stochastic block models. Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer |
| 2021 | SNARGs for $\mathcal{P}$ from LWE. Arka Rai Choudhuri, Abhishek Jain, Zhengzhong Jin |
| 2021 | Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning. Yuanzhi Li, Ruosong Wang, Lin F. Yang |
| 2021 | Sharp Thresholds in Random Simple Temporal Graphs. Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev |
| 2021 | Sharper bounds on the Fourier concentration of DNFs. Victor Lecomte, Li-Yang Tan |
| 2021 | Small-space and streaming pattern matching with $k$ edits. Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya |
| 2021 | Smoothed Analysis with Adaptive Adversaries. Nika Haghtalab, Tim Roughgarden, Abhishek Shetty |
| 2021 | Spectral Hypergraph Sparsifiers of Nearly Linear Size. Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
| 2021 | Spectral Independence via Stability and Applications to Holant-Type Problems. Zongchen Chen, Kuikui Liu, Eric Vigoda |
| 2021 | Statistically Near-Optimal Hypothesis Selection. Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran |
| 2021 | Stochastic and Worst-Case Generalized Sorting Revisited. William Kuszmaul, Shyam Narayanan |
| 2021 | Sum-of-Squares Lower Bounds for Sparse Independent Set. Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu |
| 2021 | Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas |
| 2021 | Terminal Embeddings in Sublinear Time. Yeshwanth Cherapanamjeri, Jelani Nelson |
| 2021 | Testability of relations between permutations. Oren Becker, Alexander Lubotzky, Jonathan Mosheiff |
| 2021 | The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials. Guy Bresler, Brice Huang |
| 2021 | The Hardest Explicit Construction. Oliver Korten |
| 2021 | The Minimum Formula Size Problem is (ETH) Hard. Rahul Ilango |
| 2021 | The Reachability Problem for Petri Nets is Not Primitive Recursive. Jérôme Leroux |
| 2021 | The supersingular isogeny path and endomorphism ring problems are equivalent. Benjamin Wesolowski |
| 2021 | The zero-rate threshold for adversarial bit-deletions is less than 1/2. Venkatesan Guruswami, Xiaoyu He, Ray Li |
| 2021 | Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. David P. Woodruff, Samson Zhou |
| 2021 | Tight Bounds for General Computation in Noisy Broadcast Networks. Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
| 2021 | Tight Space Complexity of the Coin Problem. Mark Braverman, Sumegha Garg, Or Zamir |
| 2021 | Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. Soheil Behnezhad |
| 2021 | Towards the sampling Lovász Local Lemma. Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong |
| 2021 | Tradeoffs for small-depth Frege proofs. Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan |
| 2021 | Unambiguous DNFs and Alon-Saks-Seymour. Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari |
| 2021 | Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. Kyle W. Burke, Matthew T. Ferland, Shang-Hua Teng |