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)

  • 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 (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 Polynomial-Time Computations 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. Improved robustness of quantum supremacy for random circuit sampling (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)