default search action
62nd FOCS 2021: Denver, CO, USA
- 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022. IEEE 2022, ISBN 978-1-6654-2055-6
- Nisheeth K. Vishnoi:
FOCS 2021 Preface. xvii - Vera Traub
, Rico Zenklusen:
A Better-Than-2 Approximation for Weighted Tree Augmentation. 1-12 - Samuel Fiorini, Gwenaël Joret, Stefan Weltge
Integer programs with bounded subdeterminants and two nonzeros per row. 13-24 - Wenzheng Li, Jan Vondrák:
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. 25-36 - Deeparnab Chakrabarty, Yu Chen, Sanjeev Khanna:
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. 37-48 - Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry:
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier. 49-58 - Nai-Hui Chia, Kai-Min Chung, Qipeng Liu, Takashi Yamakawa:
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round. 59-67 - Arka Rai Choudhuri, Abhishek Jain
SNARGs for $\mathcal{P}$ from LWE. 68-79 - Itai Dinur, Nathan Keller, Ohad Klein:
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR. 80-91 - Pranjal Dutta
Demystifying the border of depth-3 algebraic circuits. 92-103 - Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell:
Fooling Constant-Depth Threshold Circuits (Extended Abstract). 104-115 - Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain
Unambiguous DNFs and Alon-Saks-Seymour. 116-124 - Lijie Chen, Roei Tell:
Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise. 125-136 - Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang:
Rapid mixing of Glauber dynamics via spectral independence for all degrees. 137-148 - Zongchen Chen, Kuikui Liu, Eric Vigoda:
Spectral Independence via Stability and Applications to Holant-Type Problems. 149-160 - Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan:
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. 161-172 - Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong:
Towards the sampling Lovász Local Lemma. 173-183 - Tuukka Korhonen
A Single-Exponential Time 2-Approximation Algorithm for Treewidth. 184-192 - Hans L. Bodlaender
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. 193-204 - Dominik Scheder:
PPSZ is better than you think. 205-216 - Cory Palmer, Dömötör Pálvölgyi:
At most 3.55n stable matchings. 217-227 - Mark Braverman, Subhash Khot, Noam Lifshitz
An Invariance Principle for the Multi-slice, with Applications. 228-236 - Boris Bukh, Karthik C. S.
Applications of Random Algebraic Constructions to Hardness of Approximation. 237-244 - Sai Sandeep:
Almost Optimal Inapproximability of Multidimensional Packing Problems. 245-256 - Akash Kumar, C. Seshadhri, Andrew Stolman:
Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes. 257-268 - Oded Goldreich, Avi Wigderson:
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. 269-275 - Marco Bressan, Marc Roth
Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies. 276-285 - Oren Becker, Alexander Lubotzky, Jonathan Mosheiff
Testability of relations between permutations. 286-297 - Guy Bresler, Brice Huang:
The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials. 298-309 - Danny Nam, Allan Sly, Youngtak Sohn:
One-step replica symmetry breaking of random regular NAE-SAT. 310-318 - Arnaud Casteigts, Michael Raskin, Malte Renken
Sharp Thresholds in Random Simple Temporal Graphs. 319-326 - Emmanuel Abbe, Shuangping Li, Allan Sly:
Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron. 327-338 - Joseph S. B. Mitchell:
Approximating Maximum Independent Set for Rectangles in the Plane. 339-350 - Sándor Kisfaludi-Bak
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. 351-362 - Hung Le, Christian Wulff-Nilsen:
Optimal Approximate Distance Oracle for Planar Graphs. 363-374 - Mikkel Abrahamsen
Covering Polygons is Even Harder. 375-386 - Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer
Robust recovery for stochastic block models. 387-394 - Siqi Liu, Sidhanth Mohanty, Prasad Raghavendra:
On statistical inference when fixed points of belief propagation are unstable. 395-405 - Chris Jones, Aaron Potechin
Sum-of-Squares Lower Bounds for Sparse Independent Set. 406-416 - Enric Boix-Adserà, Guy Bresler, Frederic Koehler:
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models. 417-426 - Rahul Ilango:
The Minimum Formula Size Problem is (ETH) Hard. 427-432 - Oliver Korten:
The Hardest Explicit Construction. 433-444 - Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan:
Tradeoffs for small-depth Frege proofs. 445-456 - Heiko Dietrich
Group isomorphism is nearly-linear time for most orders. 457-467 - Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. 468-479 - Ken-ichi Kawarabayashi, Anastasios Sidiropoulos:
Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut. 480-491 - Arnold Filtser:
Hop-Constrained Metric Embeddings and their Applications. 492-503 - Anupam Gupta, Amit Kumar
A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows. 504-515 - Yu Gao, Yang P. Liu, Richard Peng:
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. 516-527 - Kyriakos Axiotis, Aleksander Madry, Adrian Vladu:
Faster Sparse Minimum Cost Flow by Electrical Flow Localization. 528-539 - Li Chen, Richard Peng, Di Wang:
2-norm Flow Diffusion in Near-Linear Time. 540-549 - Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi:
On the Power of Preconditioning in Sparse Linear Regression. 550-561 - Srinivasan Arunachalam, Alex B. Grilo, Tom Gur
Quantum learning algorithms imply circuit lower bounds. 562-573 - Sitan Chen, Jordan Cotler, Hsin-Yuan Huang
Exponential Separations Between Learning With and Without Quantum Memory. 574-585 - Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen:
Quantum soundness of testing tensor codes. 586-597 - Nolan J. Coble
Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits. 598-609 - Eshan Chattopadhyay, Jesse Goodman:
Improved Extractors for Small-Space Sources. 610-621 - Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao:
Affine Extractors for Almost Logarithmic Entropy. 622-633 - Klim Efremenko
Tight Bounds for General Computation in Noisy Broadcast Networks. 634-645 - Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. 646-657 - Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran:
A Theory of PAC Learnability of Partial Concept Classes. 658-671 - Jasper C. H. Lee, Paul Valiant:
Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$. 672-683 - Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau:
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination. 684-695 - Sitan Chen, Adam R. Klivans, Raghu Meka:
Learning Deep ReLU Networks Is Fixed-Parameter Tractable. 696-707 - Zeyu Guo
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]. 708-719 - Asaf Ferber, Matthew Kwan, Lisa Sauermann:
List-decodability with large radius for Reed-Solomon codes. 720-726 - Venkatesan Guruswami, Xiaoyu He
The zero-rate threshold for adversarial bit-deletions is less than 1/2. 727-738 - Jeremiah Blocki
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. 739-750 - Shuichi Hirahara, Mikito Nanashima:
On Worst-Case Learning in Relativized Heuristica. 751-758 - Robert Robere, Jeroen Zuiddam:
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms. 759-769 - Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira:
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. 770-780 - Tillmann Miltzow, Reinier F. Schmiermann:
On Classifying Continuous Constraint Satisfaction problems. 781-791 - Xiao Mao:
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. 792-803 - Nutan Limaye, Srikanth Srinivasan
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits. 804-814 - Paul Dütting, Tomer Ezra
Combinatorial Contracts. 815-826 - Aris Filos-Ratsikas
FIXP-membership via Convex Optimization: Games, Cakes, and Markets. 827-838 - George Christodoulou
On the Nisan-Ronen conjecture. 839-850 - Neil Olver, Leon Sering
Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time. 851-860 - Wenyu Jin, Xiaorui Sun:
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract). 861-872 - Soheil Behnezhad:
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. 873-884 - Tomasz Kociumaka
Small-space and streaming pattern matching with $k$ edits. 885-896 - John Kallaugher:
A Quantum Advantage for a Natural Streaming Problem. 897-908 - Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko
Statistically Near-Optimal Hypothesis Selection. 909-919 - Guy Blanc, Jane Lange, Mingda Qiao
Properly learning decision trees in almost polynomial time. 920-929 - Victor Lecomte, Li-Yang Tan:
Sharper bounds on the Fourier concentration of DNFs. 930-941 - Nika Haghtalab, Tim Roughgarden, Abhishek Shetty:
Smoothed Analysis with Adaptive Adversaries. 942-953 - Vitaly Feldman, Audra McMillan, Kunal Talwar:
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. 954-964 - Yuanzhi Li, Ruosong Wang, Lin F. Yang
Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning. 965-976 - Zeyuan Allen-Zhu, Yuanzhi Li:
Feature Purification: How Adversarial Training Performs Robust Deep Learning. 977-988 - Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye:
Minor Sparsifiers and the Distributed Laplacian Paradigm. 989-999 - Aaron Bernstein, Maximilian Probst Gutenberg
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. 1000-1008 - Mohsen Ghaffari, Fabian Kuhn:
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. 1009-1020 - Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams:
Hardness of Approximate Diameter: Now for Undirected Graphs. 1021-1032 - Shyan Akmal
MAJORITY-3SAT (and Related Problems) in Polynomial Time. 1033-1043 - David Doty
A time and space optimal stable population protocol solving exact majority. 1044-1055 - William Kuszmaul, Shyam Narayanan:
Stochastic and Worst-Case Generalized Sorting Revisited. 1056-1067 - Mark Braverman, Sumegha Garg, Or Zamir:
Tight Space Complexity of the Coin Problem. 1068-1079 - Dong Yeap Kang
A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects. 1080-1089 - Guillaume Moroz:
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. 1090-1099 - Benjamin Wesolowski:
The supersingular isogeny path and endomorphism ring problems are equivalent. 1100-1111 - Saugata Basu, Nathanael Cox:
Harmonic Persistent Homology (extended abstract). 1112-1123 - Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. 1124-1134 - Amir Abboud, Robert Krauthgamer
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time. 1135-1146 - Ruoxu Cen
Minimum Cuts in Directed Graphs via Partial Sparsification. 1147-1158 - Michael Kapralov
Spectral Hypergraph Sparsifiers of Nearly Linear Size. 1159-1170 - Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul:
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering. 1171-1182 - David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. 1183-1196 - Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy
Approximability of all finite CSPs with linear sketches. 1197-1208 - Yeshwanth Cherapanamjeri, Jelani Nelson:
Terminal Embeddings in Sublinear Time. 1209-1216 - Kyle W. Burke
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. 1217-1228 - Wojciech Czerwinski, Lukasz Orlikowski:
Reachability in Vector Addition Systems is Ackermann-complete. 1229-1240 - Jérôme Leroux:
The Reachability Problem for Petri Nets is Not Primitive Recursive. 1241-1252 - Anupam Gupta, Gregory Kehne, Roie Levin:
Random Order Online Set Cover is as Easy as Offline. 1253-1264 - Ruiquan Gao, Zhongtian He, Zhiyi Huang
Improved Online Correlated Selection. 1265-1276 - Guy Blanc, Moses Charikar
Multiway Online Correlated Selection. 1277-1284 - Rahul Jain, Srijita Kundu:
A direct product theorem for quantum communication complexity with applications to device-independent QKD. 1285-1295 - Yasuhiro Kondo, Ryuhei Mori
Quantum supremacy and hardness of estimating output probabilities of quantum circuits. 1296-1307 - Adam Bouland
Noise and the Frontier of Quantum Supremacy. 1308-1317
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-03 23:17 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: