| 2022 | (1+ε)-Approximate Shortest Paths in Dynamic Streams. Michael Elkin, Chhaya Trehan |
| 2022 | A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. Pu Gao, Calum MacRury, Pawel Pralat |
| 2022 | A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs. Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, Ziena Zeif |
| 2022 | A Sublinear Local Access Implementation for the Chinese Restaurant Process. Peter Mörters, Christian Sohler, Stefan Walzer |
| 2022 | A Unified Approach to Discrepancy Minimization. Nikhil Bansal, Aditi Laddha, Santosh S. Vempala |
| 2022 | Accelerating Polarization via Alphabet Extension. Iwan M. Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, Hsin-Po Wang |
| 2022 | Adaptive Sketches for Robust Regression with Importance Sampling. Sepideh Mahabadi, David P. Woodruff, Samson Zhou |
| 2022 | Affine Extractors and AC0-Parity. Xuangui Huang, Peter Ivanov, Emanuele Viola |
| 2022 | Approximating CSPs with Outliers. Suprovat Ghoshal, Anand Louis |
| 2022 | Approximating LCS and Alignment Distance over Multiple Sequences. Debarati Das, Barna Saha |
| 2022 | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), September 19-21, 2022 Amit Chakrabarti, Chaitanya Swamy |
| 2022 | Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting. Sepehr Assadi, Hoai-An Nguyen |
| 2022 | Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions. Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, Ke Wu |
| 2022 | Black-Box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial Time. Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay |
| 2022 | Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2022 | Caching with Reserves. Sharat Ibrahimpur, Manish Purohit, Zoya Svitkina, Erik Vee, Joshua R. Wang |
| 2022 | Communication Complexity of Collision. Mika Göös, Siddhartha Jain |
| 2022 | Cover and Hitting Times of Hyperbolic Random Graphs. Marcos Kiwi, Markus Schepers, John Sylvester |
| 2022 | Double Balanced Sets in High Dimensional Expanders. Tali Kaufman, David Mass |
| 2022 | Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, Ruizhe Zhang |
| 2022 | Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing. Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen |
| 2022 | Fair Correlation Clustering in General Graphs. Roy Schwartz, Roded Zats |
| 2022 | Fast and Perfect Sampling of Subgraphs and Polymer Systems. Antonio Blanca, Sarah Cannon, Will Perkins |
| 2022 | Finding the KT Partition of a Weighted Graph in Near-Linear Time. Simon Apers, Pawel Gawrychowski, Troy Lee |
| 2022 | Fourier Growth of Regular Branching Programs. Chin Ho Lee, Edward Pyne, Salil P. Vadhan |
| 2022 | Hardness Results for Weaver's Discrepancy Problem. Daniel A. Spielman, Peng Zhang |
| 2022 | High Dimensional Expansion Implies Amplified Local Testability. Tali Kaufman, Izhar Oppenheim |
| 2022 | Hyperbolic Concentration, Anti-Concentration, and Discrepancy. Zhao Song, Ruizhe Zhang |
| 2022 | Improved Bounds for Randomly Colouring Simple Hypergraphs. Weiming Feng, Heng Guo, Jiaheng Wang |
| 2022 | Improved Local Testing for Multiplicity Codes. Dan Karliner, Amnon Ta-Shma |
| 2022 | Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling. Takuro Fukunaga |
| 2022 | Learning Generalized Depth Three Arithmetic Circuits in the Non-Degenerate Case. Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha |
| 2022 | Lifting with Inner Functions of Polynomial Discrepancy. Yahel Manor, Or Meir |
| 2022 | Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems. Hridesh Kedia, Shunhao Oh, Dana Randall |
| 2022 | Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. Hermish Mehta, Daniel Reichman |
| 2022 | Lower Bound Methods for Sign-Rank and Their Limitations. Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao |
| 2022 | Massively Parallel Algorithms for Small Subgraph Counting. Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, Slobodan Mitrovic |
| 2022 | Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint. Max Klimm, Martin Knaack |
| 2022 | Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream Model. Moran Feldman, Ariel Szarf |
| 2022 | On Sketching Approximations for Symmetric Boolean CSPs. Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy |
| 2022 | Online Facility Location with Linear Delay. Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Jan Marcinkowski |
| 2022 | Ordered k-Median with Outliers. Shichuan Deng, Qianfan Zhang |
| 2022 | Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan |
| 2022 | Prophet Matching in the Probe-Commit Model. Allan Borodin, Calum MacRury, Akash Rakheja |
| 2022 | Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. Venkatesan Guruswami, Xin Lyu, Xiuhan Wang |
| 2022 | Relative Survivable Network Design. Michael Dinitz, Ama Koranteng, Guy Kortsarz |
| 2022 | Sampling from Potts on Random Graphs of Unbounded Degree via Random-Cluster Dynamics. Antonio Blanca, Reza Gheissari |
| 2022 | Sketching Approximability of (Weak) Monarchy Predicates. Chi-Ning Chou, Alexander Golovnev, Amirbehshad Shahrasbi, Madhu Sudan, Santhoshini Velusamy |
| 2022 | Sketching Distances in Monotone Graph Classes. Louis Esperet, Nathaniel Harms, Andrey Kupavskii |
| 2022 | Some Results on Approximability of Minimum Sum Vertex Cover. Aleksa Stankovic |
| 2022 | Space Optimal Vertex Cover in Dynamic Streams. Kheeran K. Naidu, Vihan Shah |
| 2022 | Streaming Algorithms with Large Approximation Factors. Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang |
| 2022 | Submodular Dominance and Applications. Frederick Qiu, Sahil Singla |
| 2022 | The Biased Homogeneous r-Lin Problem. Suprovat Ghoshal |
| 2022 | Tight Chernoff-Like Bounds Under Limited Independence. Maciej Skorski |
| 2022 | Unbalanced Expanders from Multiplicity Codes. Itay Kalev, Amnon Ta-Shma |