FOCS 2021 Accepted Papers

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

Tuukka Korhonen. A Single-Exponential Time 2-Approximation Algorithm for Treewidth (Full version)

Mina Dalirrooyfard, Ray Li and Virginia Vassilevska Williams. Hardness of approximate Diameter: now for undirected graphs (Full version)

Yeshwanth Cherapanamjeri and Jelani Nelson. Terminal Embeddings in Sublinear Time (Full version)

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

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

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

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

Pooya Hatami, William Hoza, Avishay Tal and Roei Tell. Fooling Constant-Depth Threshold Circuits (Full version)

Sai Sandeep. Almost Optimal Inapproximability of Multidimensional Packing Problems (Full version)

Vera Traub and Rico Zenklusen. A Better-Than-2 Approximation for Weighted Tree Augmentation (Full version)

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

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

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 (Full version)

Dominik Scheder. PPSZ is better than you think (Full version)

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 (Full version)

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

Wojciech Czerwiński and Łukasz Orlikowski. Reachability in Vector Addition Systems is Ackermann-complete (Full version)

Oded Goldreich and Avi Wigderson. Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model (Full version)

Arnold Filtser. Hop-Constrained Metric Embeddings and their Applications (Full version)

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

Pranjal Dutta, Prateek Dwivedi and Nitin Saxena. Demystifying the border of depth-3 algebraic circuits (Full version)

Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent (Full version)

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

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

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

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

Jingqiu Ding, Tommaso D’Orsi, Rajai Nasser and David Steurer. Robust Recovery for Stochastic Block Models (Full version)

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

James Wilson and Heiko Dietrich. Group isomorphism is nearly-linear time for most orders (Full version)

Mikkel Abrahamsen. Covering Polygons is Even Harder (Full version)

Asaf Ferber, Matthew Kwan and Lisa Sauermann. List-decodability with large radius for Reed-Solomon codes (Full version)

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

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

Till Miltzow and Reinier Schmiermann. On Classifying Continuous Constraint Satisfaction problems (Full version)

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

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

Boris Bukh, Karthik C. S. and Bhargav Narayanan. Applications of random algebraic constructions to hardness of approximation (Full version)

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

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 (Full version)

Lijie Chen and Roei Tell. Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise (Full version)

Zongchen Chen, Kuikui Liu and Eric Vigoda. Spectral Independence via Stability and Applications to Holant-Type Problems (Full version)

Lijie Chen, Ce Jin, Rahul Santhanam and Ryan Williams. Constructive Separations and Their Consequences (Full version)

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

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

William Kuszmaul and Shyam Narayanan. Stochastic and Worst-Case Generalized Sorting Revisited (Full version)

Hung Le and Christian Wulff-Nilsen. Optimal Approximate Distance Oracle for Planar Graphs (Full version)

Robert Robere and Jeroen Zuiddam. Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms (Full version)

David P. Woodruff and Samson Zhou. Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators (Full version)

Anupam Gupta, Gregory Kehne and Roie Levin. Random Order Set Cover is as Easy as Offline (Full version)

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

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

George Christodoulou, Elias Koutsoupias and Annamaria Kovacs. On the Nisan-Ronen conjecture (Full version)

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 (Full version)

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

Victor Lecomte and Li-Yang Tan. Sharper bounds on the Fourier concentration of DNFs (Full version)

Noga Alon, Steve Hanneke, Ron Holzman and Shay Moran. A Theory of PAC Learnability of Partial Concept Classes (Full version)

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

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

Guy Bresler and Brice Huang. The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials (Full version)

Tomasz Kociumaka, Ely Porat and Tatiana Starikovskaya. Small space and streaming pattern matching with k edits (Full version)

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

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

Oliver Korten. The Hardest Explicit Construction (Full version)

Li Chen, Richard Peng and Di Wang. 2-Norm Flow Diffusion in Near-Linear Time (Full version)

Oren Becker, Alexander Lubotzky and Jonathan Mosheiff. Testability of relations between permutations (Full version)

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

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

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

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

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

Sitan Chen, Adam Klivans and Raghu Meka. Learning Deep ReLU Networks Is Fixed-Parameter Tractable (Full version)

Emmanuel Abbe, Shuangping Li and Allan Sly. Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron (Full version)

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

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

Toniann Pitassi, Prasanna Ramakrishnan and Li-Yang Tan. Tradeoffs for small-depth Frege proofs (Full version)

Shuichi Hirahara and Mikito Nanashima. On Worst-Case Learning in Relativized Heuristica (Full version)

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

Mohsen Ghaffari and Fabian Kuhn. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition (Full version)

Jérôme Leroux. The Reachability Problem for Petri Nets is Not Primitive Recursive (Full version)

Paul Dutting, Tomer Ezra, Michal Feldman and Thomas Kesselheim. Combinatorial Contracts (Full version)

Michael Kapralov, Robert Krauthgamer, Jakab Tardos and Yuichi Yoshida. Spectral Hypergraph Sparsifiers of Nearly Linear Size (Full version)

Saugata Basu and Nathanael Cox. Harmonic Persistent Homology (Full version)

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

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

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

Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan and Yan Zhong. Improved Online Correlated Selection (Full version)

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

Eshan Chattopadhyay and Jesse Goodman. Improved Extractors for Small-Space Sources (Full version)

Eshan Chattopadhyay, Jesse Goodman and Jyun-Jie Liao. Affine Extractors for Almost Logarithmic Entropy (Full version)

Wenyu Jin and Xiaorui Sun. Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Full version)

Joseph Mitchell. Approximating Maximum Independent Set for Rectangles in the Plane (Full version)

Arnaud Casteigts, Mikhail Raskin, Malte Renken and Viktor Zamaraev. Sharp Thresholds in Random Simple Temporal Graphs (Full version)

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen. Quantum soundness of testing tensor codes (Full version)

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

Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol and Shay Moran. Statistically Near-Optimal Hypothesis Selection (Full version)

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

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

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

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

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

Mark Braverman, Sumegha Garg and Or Zamir. Tight Space Complexity of the Coin Problem (Full version)

Soheil Behnezhad. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover (Full version)

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

Guy Blanc and Moses Charikar. Multiway Online Correlated Selection (Full version)

Arka Rai Choudhuri, Abhishek Jain and Zhengzhong Jin. SNARGs for P from LWE (Full version)

John Kallaugher. A Quantum Advantage for a Natural Streaming Problem (Full version)

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

Nika Haghtalab, Tim Roughgarden and Abhishek Shetty. Smoothed Analysis with Adaptive Adversaries (Full version)

Kyriakos Axiotis, Aleksander Mądry and Adrian Vladu. Faster Sparse Minimum Cost Flow by Electrical Flow Localization (Full version)

Wenzheng Li and Jan Vondrak. A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations (Full version)

Zeyuan Allen-Zhu and Yuanzhi Li. Feature Purification: How Adversarial Training Performs Robust Deep Learning (Full version)

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

Adam Bouland, Bill Fefferman, Zeph Landau and Yunchao Liu. Noise and the frontier of quantum supremacy (Full version)

Yasuhiro Kondo, Ryuhei Mori and Ramis Movassagh. Quantum supremacy and hardness of estimating output probabilities of quantum circuits (Full version)

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

Jasper C.H. Lee and Paul Valiant. Optimal Sub-Gaussian Mean Estimation in R (Full version)