FOCS 2021 Accepted Papers

  • Vishesh Jain, Huy Tuan Pham and Thuy-Duong Vuong. Towards the sampling Lovász Local Lemma

  • Tuukka Korhonen. A Single-Exponential Time 2-Approximation Algorithm for Treewidth

  • Mina Dalirrooyfard, Ray Li and Virginia Vassilevska Williams. Hardness of approximate Diameter: now for undirected graphs

  • Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal Embeddings in Sublinear Time

  • Xiao Mao. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

  • Marco Bressan and Marc Roth. Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies

  • Danny Nam, Allan Sly and Youngtak Sohn. One-step replica symmetry breaking of random regular NAE-SAT

  • Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer. An Invariance Principle for the Multi-slice, with Applications

  • Pooya Hatami, William Hoza, Avishay Tal and Roei Tell. Fooling Constant-Depth Threshold Circuits

  • Sai Sandeep. Almost Optimal Inapproximability of Multidimensional Packing Problems

  • Vera Traub and Rico Zenklusen. A Better-Than-2 Approximation for Weighted Tree Augmentation

  • Venkatesan Guruswami, Xiaoyu He and Ray Li. The zero-rate threshold for adversarial bit-deletions is less than 1/2

  • Hans L. Bodlaender, Carla Groenland, Jesper Nederlof and Celine M. F. Swennenhuis. Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

  • Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis and Mikkel Thorup. Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

  • Dominik Scheder. PPSZ is better than you think

  • Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku and Deryk Osthus. A proof of the Erdős–Faber–Lovász conjecture: Algorithmic aspects

  • Nai-Hui Chia, Kai-Min Chung, Qipeng Liu and Takashi Yamakawa. On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds

  • Wojciech Czerwiński and Łukasz Orlikowski. Reachability in Vector Addition Systems is Ackermann-complete

  • Oded Goldreich and Avi Wigderson. Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

  • Arnold Filtser. Hop-Constrained Metric Embeddings and their Applications

  • Ken-Ichi Kawarabayashi and Anastasios Sidiropoulos. Embeddings of Planar Quasimetrics into Directed \ell_1 and Polylogarithmic Approximation for Directed Sparsest-Cut

  • Pranjal Dutta, Prateek Dwivedi and Nitin Saxena. Demystifying the border of depth-3 algebraic circuits

  • Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent

  • Xiaoyu Chen, Weiming Feng, Yitong Yin and Xinyuan Zhang. Rapid mixing of Glauber dynamics via spectral independence for all degrees

  • Mika Göös, Shalev Ben-David, Robin Kothari, Siddhartha Jain and Kaspars Balodis. Unambiguous DNFs and Alon-Saks-Seymour

  • Chi-Ning Chou, Alexander Golovnev, Madhu Sudan and Santhoshini Velusamy. Approximability of all finite CSPs with linear sketches

  • Dorna Abdolazimi, Kuikui Liu and Shayan Oveis Gharan. A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings

  • Jingqiu Ding, Tommaso D’Orsi, Rajai Nasser and David Steurer. Robust Recovery for Stochastic Block Models

  • Marco Carmosino, Valentine Kabanets, Antonina Kolokolova and Igor C. Oliveira. LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic

  • James Wilson and Heiko Dietrich. Group isomorphism is nearly-linear time for most orders

  • Mikkel Abrahamsen. Covering Polygons is Even Harder

  • Asaf Ferber, Matthew Kwan and Lisa Sauermann. List-decodability with large radius for Reed-Solomon codes

  • Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh and Alexandros Hollender. FIXP-membership via Convex Optimization: Games, Cakes, and Markets

  • Samuel Fiorini, Gwenaël Joret, Stefan Weltge and Yelena Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row

  • Till Miltzow and Reinier Schmiermann. On Classifying Continuous Constraint Satisfaction problems

  • Aaron Bernstein, Maximilian Probst Gutenberg and Thatchaphol Saranurak. Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time

  • Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun and Mingquan Ye. Minor Sparsifiers and the Distributed Laplacian Paradigm

  • Boris Bukh, Karthik C. S. and Bhargav Narayanan. Applications of random algebraic constructions to hardness of approximation

  • Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng and Minshen Zhu. Exponential Lower Bounds for Locally Decodable Codes Correcting Insertions and Deletions

  • David Doty, Mahsa Eftekhari Hesari, Leszek Gąsieniec, Eric Severson, Grzegorz Stachowiak and Przemysław Uznański. A time and space optimal stable population protocol solving exact majority

  • Lijie Chen and Roei Tell. Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

  • Zongchen Chen, Kuikui Liu and Eric Vigoda. Spectral Independence via Stability and Applications to Holant-Type Problems

  • Lijie Chen, Ce Jin, Rahul Santhanam and Ryan Williams. Constructive Separations and Their Consequences

  • Jonathan Kelner, Frederic Koehler, Raghu Meka and Dhruv Rohatgi. On the Power of Preconditioning in Sparse Linear Regression

  • Jason Li, Debmalya Panigrahi and Thatchaphol Saranurak. A Nearly Optimal All Pairs Minimum Cuts Algorithm in Simple Graphs

  • William Kuszmaul and Shyam Narayanan. Stochastic and Worst-Case Generalized Sorting Revisited

  • Hung Le and Christian Wulff-Nilsen. Optimal Approximate Distance Oracle for Planar Graphs

  • Robert Robere and Jeroen Zuiddam. Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

  • David P. Woodruff and Samson Zhou. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators

  • Anupam Gupta, Gregory Kehne and Roie Levin. Random Order Set Cover is as Easy as Offline

  • Sándor Kisfaludi-Bak, Jesper Nederlof and Karol Węgrzycki. A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

  • Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira and Aarthi Sundaram. Quantum learning algorithms imply circuit lower bounds

  • George Christodoulou, Elias Koutsoupias and Annamaria Kovacs. On the Nisan-Ronen conjecture

  • Akash Kumar, C. Seshadhri and Andrew Stolman. Random walks and forbidden minors III: poly(d\eps^{-1})-time partition oracles for minor-free graph classes

  • Matthew Coudron and Nolan Coble. Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits.

  • Victor Lecomte and Li-Yang Tan. Sharper bounds on the Fourier concentration of DNFs

  • Noga Alon, Steve Hanneke, Ron Holzman and Shay Moran. A Theory of PAC Learnability of Partial Concept Classes

  • Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo and Mary Wootters. Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

  • Anupam Gupta, Amit Kumar and Debmalya Panigrahi. A Hitting Set Relaxation for k-Server and an Extension to Time-Windows

  • Guy Bresler and Brice Huang. The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials

  • Tomasz Kociumaka, Ely Porat and Tatiana Starikovskaya. Small space and streaming pattern matching with k edits

  • Enric Boix-Adserà, Guy Bresler and Frederic Koehler. Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models

  • Yu Gao, Yang P. Liu and Richard Peng. Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao

  • Oliver Korten. The Hardest Explicit Construction

  • Li Chen, Richard Peng and Di Wang. 2-Norm Flow Diffusion in Near-Linear Time

  • Oren Becker, Alexander Lubotzky and Jonathan Mosheiff. Testability of relations between permutations

  • Guy Blanc, Jane Lange, Mingda Qiao and Li-Yang Tan. Properly learning decision trees in almost polynomial time

  • Guillaume Moroz. New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems

  • Kyle Burke, Matthew Ferland and Shang-Hua Teng. Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography

  • Sitan Chen, Frederic Koehler, Ankur Moitra and Morris Yau. Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination

  • Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani and Jeff Xu. Sum-of-Squares Lower Bounds for Sparse Independent Set

  • Sitan Chen, Adam Klivans and Raghu Meka. Learning Deep ReLU Networks Is Fixed-Parameter Tractable

  • Emmanuel Abbe, Shuangping Li and Allan Sly. Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron

  • Sitan Chen, Jordan Cotler, Hsin-Yuan Huang and Jerry Li. Exponential Separations Between Learning With and Without Quantum Memory

  • Alessandro Chiesa, Fermi Ma, Nicholas Spooner and Mark Zhandry. Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

  • Toniann Pitassi, Prasanna Ramakrishnan and Li-Yang Tan. Tradeoffs for small-depth Frege proofs

  • Shuichi Hirahara and Mikito Nanashima. On Worst-Case Learning in Relativized Heuristica

  • Cory Palmer and Dömötör Pálvölgyi. At most 3.55^n stable matchings

  • Mohsen Ghaffari and Fabian Kuhn. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition

  • Jérôme Leroux. The Reachability Problem for Petri Nets is Not Primitive Recursive

  • Paul Dutting, Tomer Ezra, Michal Feldman and Thomas Kesselheim. Combinatorial Contracts

  • Michael Kapralov, Robert Krauthgamer, Jakab Tardos and Yuichi Yoshida. Spectral Hypergraph Sparsifiers of Nearly Linear Size

  • Saugata Basu and Nathanael Cox. Harmonic Persistent Homology

  • Amir Abboud, Robert Krauthgamer and Ohad Trabelsi. APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time

  • Rahul Jain and Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent QKD

  • Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

  • Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan and Yan Zhong. Improved Online Correlated Selection

  • Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Kent Quanrud and Thatchaphol Saranurak. Minimum Cuts in Directed Graphs via Partial Sparsification

  • Eshan Chattopadhyay and Jesse Goodman. Improved Extractors for Small-Space Sources

  • Eshan Chattopadhyay, Jesse Goodman and Jyun-Jie Liao. Affine Extractors for Almost Logarithmic Entropy

  • Wenyu Jin and Xiaorui Sun. Fully Dynamic s-t Edge Connectivity in Subpolynomial Time

  • Joseph Mitchell. Approximating Maximum Independent Set for Rectangles in the Plane

  • Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson and John Wright. Unique Games hardness of the quantum Heisenberg model, and a vector-valued Borell’s inequality

  • Arnaud Casteigts, Mikhail Raskin, Malte Renken and Viktor Zamaraev. Sharp Thresholds in Random Simple Temporal Graphs

  • Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen. Quantum soundness of testing tensor codes

  • Michael A. Bender, Bradley C. Kuszmaul and William Kuszmaul. Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

  • Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol and Shay Moran. Statistically Near-Optimal Hypothesis Selection

  • Siqi Liu, Sidhanth Mohanty and Prasad Raghavendra. On statistical inference when fixed points of belief propagation are unstable

  • Klim Efremenko, Gillat Kol, Dmitry Paramonov and Raghuvansh Saxena. Tight Bounds for General Computation in Noisy Broadcast Networks

  • Rahul Ilango. The Minimum Formula Size Problem is (ETH) Hard

  • Itai Dinur, Nathan Keller and Ohad Klein. Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR

  • Deeparnab Chakrabarty, Yu Chen and Sanjeev Khanna. A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

  • Mark Braverman, Sumegha Garg and Or Zamir. Tight Space Complexity of the Coin Problem

  • Soheil Behnezhad. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

  • Shyan Akmal and Ryan Williams. MAJORITY-3SAT (and Related Problems) in Polynomial Time

  • Guy Blanc and Moses Charikar. Multiway Online Correlated Selection

  • Arka Rai Choudhuri, Abhishek Jain and Zhengzhong Jin. SNARGs for Polynomial-Time Computations from LWE

  • John Kallaugher. A Quantum Advantage for a Natural Streaming Problem

  • Yuanzhi Li, Ruosong Wang and Lin Yang. Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning

  • Nika Haghtalab, Tim Roughgarden and Abhishek Shetty. Smoothed Analysis with Adaptive Adversaries

  • Kyriakos Axiotis, Aleksander Mądry and Adrian Vladu. Faster Sparse Minimum Cost Flow by Electrical Flow Localization

  • Wenzheng Li and Jan Vondrak. A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations

  • Zeyuan Allen-Zhu and Yuanzhi Li. Feature Purification: How Adversarial Training Performs Robust Deep Learning

  • Vitaly Feldman, Audra McMillan and Kunal Talwar. Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling

  • Adam Bouland, Bill Fefferman, Zeph Landau and Yunchao Liu. Noise and the frontier of quantum supremacy

  • Yasuhiro Kondo, Ryuhei Mori and Ramis Movassagh. Improved robustness of quantum supremacy for random circuit sampling

  • Neil Olver, Leon Sering and Laura Vargas Koch. Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time

  • Jasper C.H. Lee and Paul Valiant. Optimal Sub-Gaussian Mean Estimation in R