| 2022 | 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 |
| 2022 | A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP. Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
| 2022 | A Characterization of Multiclass Learnability. Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff |
| 2022 | A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits. William Kuszmaul |
| 2022 | A Proof of the Kahn-Kalai Conjecture. Jinyoung Park, Huy Tuan Pham |
| 2022 | A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D. Marvin Künnemann |
| 2022 | Active Linear Regression for ℓp Norms and Beyond. Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda |
| 2022 | Algorithms and Barriers in the Symmetric Binary Perceptron Model. David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu |
| 2022 | Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure. Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu |
| 2022 | Algorithms for the ferromagnetic Potts model on expanders. Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, Corrine Yap |
| 2022 | Almost 3-Approximate Correlation Clustering in Constant Rounds. Soheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang Tan |
| 2022 | Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson |
| 2022 | An Approximate Generalization of the Okamura-Seymour Theorem. Nikhil Kumar |
| 2022 | Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles. Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams, Nicole Wein |
| 2022 | Balanced Allocations: The Heavily Loaded Case with Deletions. Nikhil Bansal, William Kuszmaul |
| 2022 | Binary Codes with Resilience Beyond 1/4 via Interaction. Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang |
| 2022 | Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing. Namiko Matsumoto, Arya Mazumdar |
| 2022 | Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time. Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Ohad Trabelsi |
| 2022 | Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues. Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung |
| 2022 | Classical Verification of Quantum Computations in Linear Time. Jiayu Zhang |
| 2022 | Computing in Anonymous Dynamic Networks Is Linear. Giuseppe Antonio Di Luna, Giovanni Viglietta |
| 2022 | Constant Approximation of Min-Distances in Near-Linear Time. Shiri Chechik, Tianyi Zhang |
| 2022 | Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures. Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan |
| 2022 | Correlation Clustering with Sherali-Adams. Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman |
| 2022 | Cut Query Algorithms with Star Contraction. Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2022 | Derandomizing Directed Random Walks in Almost-Linear Time. Rasmus Kyng, Simon Meierhans, Maximilian Probst |
| 2022 | Determinant Maximization via Matroid Intersection Algorithms. Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali |
| 2022 | Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler |
| 2022 | Deterministic Small Vertex Connectivity in Almost Linear Time. Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai |
| 2022 | Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs. Laxman Dhulipala, Quanquan C. Liu, Sofya Raskhodnikova, Jessica Shi, Julian Shun, Shangdi Yu |
| 2022 | Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits. Ronen Shaltiel, Jad Silbak |
| 2022 | Estimating the Longest Increasing Subsequence in Nearly Optimal Time. Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein |
| 2022 | Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares. Max Hopkins, Ting-Chun Lin |
| 2022 | Factorial Lower Bounds for (Almost) Random Order Streams. Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price |
| 2022 | Fast Deterministic Fully Dynamic Distance Approximation. Jan van den Brand, Sebastian Forster, Yasamin Nazari |
| 2022 | Fast Multivariate Multipoint Evaluation Over All Finite Fields. Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans |
| 2022 | Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices. Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
| 2022 | First Price Auction is 1 - 1 /e Yaonan Jin, Pinyan Lu |
| 2022 | Fitting Metrics and Ultrametrics with Minimum Disagreements. Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee, Arnaud de Mesmay |
| 2022 | Fooling polynomials using invariant theory Harm Derksen, Emanuele Viola |
| 2022 | Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2022 | Generalised entropy accumulation. Tony Metger, Omar Fawzi, David Sutter, Renato Renner |
| 2022 | Geometry of Secure Two-party Computation. Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji, Hai H. Nguyen |
| 2022 | Hardness Self-Amplification from Feasible Hard-Core Sets. Shuichi Hirahara, Nobutaka Shimizu |
| 2022 | Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets. Shimon Kogan, Merav Parter |
| 2022 | High-Dimensional Geometric Streaming in Polynomial Space. David P. Woodruff, Taisuke Yasuda |
| 2022 | Improved Lower Bounds for Submodular Function Minimization. Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford |
| 2022 | Improved Optimal Testing Results from Global Hypercontractivity. Tali Kaufman, Dor Minzer |
| 2022 | Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. Alexander Meiburg |
| 2022 | Incrementally Verifiable Computation via Rate-1 Batch Arguments. Omer Paneth, Rafael Pass |
| 2022 | Indistinguishability Obfuscation via Mathematical Proofs of Equivalence. Abhishek Jain, Zhengzhong Jin |
| 2022 | Induced Cycles and Paths Are Harder Than You Think. Mina Dalirrooyfard, Virginia Vassilevska Williams |
| 2022 | Interior point methods are not worse than Simplex. Xavier Allamigeon, Daniel Dadush, Georg Loho, Bento Natura, László A. Végh |
| 2022 | Killing a vortex. Dimitrios M. Thilikos, Sebastian Wiederrecht |
| 2022 | Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds. Manik Dhar, Zeev Dvir |
| 2022 | Local Computation of Maximal Independent Set. Mohsen Ghaffari |
| 2022 | Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract). Yuansi Chen, Ronen Eldan |
| 2022 | Low Treewidth Embeddings of Planar and Minor-Free Metrics. Arnold Filtser, Hung Le |
| 2022 | Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva |
| 2022 | Memory Bounds for Continual Learning. Xi Chen, Christos H. Papadimitriou, Binghui Peng |
| 2022 | Minimax Rates for Robust Community Detection. Allen Liu, Ankur Moitra |
| 2022 | Motif Cut Sparsifiers. Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler, Jakab Tardos |
| 2022 | NP-Hardness of Learning Programs and Partial MCSP. Shuichi Hirahara |
| 2022 | Near-Optimal Deterministic Vertex-Failure Connectivity Oracles. Yaowei Long, Thatchaphol Saranurak |
| 2022 | Nearly Optimal Communication and Query Complexity of Bipartite Matching. Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai |
| 2022 | Negative-Weight Single-Source Shortest Paths in Near-linear Time. Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen |
| 2022 | New Additive Spanner Lower Bounds by an Unlayered Obstacle Product. Greg Bodwin, Gary Hoppenworth |
| 2022 | On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. Johan Håstad, Kilian Risse |
| 2022 | On Matrix Multiplication and Polynomial Identity Testing. Robert Andrews |
| 2022 | On Weighted Graph Sparsification by Linear Sketching. Yu Chen, Sanjeev Khanna, Huan Li |
| 2022 | On the Range Avoidance Problem for Circuits. Hanlin Ren, Rahul Santhanam, Zhikun Wang |
| 2022 | Online List Labeling: Breaking the log Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein |
| 2022 | Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence. Nima Anari, Yang P. Liu, Thuy-Duong Vuong |
| 2022 | Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. Jeongwan Haah, Robin Kothari, Ewin Tang |
| 2022 | Optimal mixing for two-state anti-ferromagnetic spin systems. Xiaoyu Chen, Weiming Feng, Yitong Yin, Xinyuan Zhang |
| 2022 | Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design. Bo Peng, Zhihao Gavin Tang |
| 2022 | Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. Joao Basso, David Gamarnik, Song Mei, Leo Zhou |
| 2022 | Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]. Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, Or Zamir |
| 2022 | Polynomial-Time Power-Sum Decomposition of Polynomials. Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu |
| 2022 | Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably. Alex Lombardi, Fermi Ma, Nicholas Spooner |
| 2022 | Properly learning monotone functions via local correction. Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan |
| 2022 | Punctured Low-Bias Codes Behave Like Random Linear Codes. Venkatesan Guruswami, Jonathan Mosheiff |
| 2022 | Pure-Circuit: Strong Inapproximability for PPAD. Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
| 2022 | Quantum Tanner codes. Anthony Leverrier, Gilles Zémor |
| 2022 | Radical Sylvester-Gallai Theorem for Cubics. Rafael Oliveira, Akash Kumar Sengupta |
| 2022 | Randomised Composition and Small-Bias Minimax. Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre |
| 2022 | Rate-1 Non-Interactive Arguments for Batch-NP and Applications. Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan |
| 2022 | Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring. Gil Cohen, Tal Yankovitz |
| 2022 | Rounds vs Communication Tradeoffs for Maximal Independent Sets. Sepehr Assadi, Gillat Kol, Zhijun Zhang |
| 2022 | Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time. Kun He, Chunyang Wang, Yitong Yin |
| 2022 | Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. Ahmed El Alaoui, Andrea Montanari, Mark Sellke |
| 2022 | Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. Pranjal Dutta, Nitin Saxena |
| 2022 | Separations in Proof Complexity and TFNP. Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao |
| 2022 | Shortest Paths without a Map, but with an Entropic Regularizer. Sébastien Bubeck, Christian Coester, Yuval Rabani |
| 2022 | Simple Hard Instances for Low-Depth Algebraic Proofs. Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret |
| 2022 | Solving SDP Faster: A Robust IPM Framework and Efficient Implementation. Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang |
| 2022 | Solving the Hamilton cycle problem fast on average. Michael Anastos |
| 2022 | Sparse random hypergraphs: Non-backtracking spectra and community detection. Ludovic Stephan, Yizhe Zhu |
| 2022 | Streaming Facility Location in High Dimension via Geometric Hashing. Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, Mingwei Yang |
| 2022 | Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract). Huacheng Yu |
| 2022 | Survivable Network Design Revisited: Group-Connectivity. Qingyun Chen, Bundit Laekhanukit, Chao Liao, Yuhao Zhang |
| 2022 | Testing Positive Semidefiniteness Using Linear Measurements. Deanna Needell, William Swartworth, David P. Woodruff |
| 2022 | The Implicit Graph Conjecture is False. Hamed Hatami, Pooya Hatami |
| 2022 | The Power of Uniform Sampling for Coresets. Vladimir Braverman, Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, Xuan Wu |
| 2022 | The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. John Kallaugher, Ojas Parekh |
| 2022 | Tight Bounds for Quantum State Certification with Incoherent Measurements. Sitan Chen, Jerry Li, Brice Huang, Allen Liu |
| 2022 | Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses. Brice Huang, Mark Sellke |
| 2022 | Unstructured Hardness to Average-Case Randomness. Lijie Chen, Ron D. Rothblum, Roei Tell |
| 2022 | Verifiable Quantum Advantage without Structure. Takashi Yamakawa, Mark Zhandry |
| 2022 | What is in #P and what is not? Christian Ikenmeyer, Igor Pak |
| 2022 | Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance. Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh |