| 2022 | (Fractional) online stochastic matching via fine-grained offline statistics. Zhihao Gavin Tang, Jinzhao Wu, Hongxun Wu |
| 2022 | 3.1 Jiatu Li, Tianqi Yang |
| 2022 | A PTAS for unsplittable flow on a path. Fabrizio Grandoni, Tobias Mömke, Andreas Wiese |
| 2022 | A characterization of approximability for biased CSPs. Euiwoong Lee, Suprovat Ghoshal |
| 2022 | A new framework for matrix discrepancy: partial coloring bounds via mirror descent. Daniel Dadush, Haotian Jiang, Victor Reis |
| 2022 | A strong version of Cobham's theorem. Philipp Hieronymi, Christian Schulz |
| 2022 | A subpolynomial approximation algorithm for graph crossing number in low-degree graphs. Julia Chuzhoy, Zihan Tan |
| 2022 | Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2022 | Almost-linear Hsien-Chih Chang, Robert Krauthgamer, Zihan Tan |
| 2022 | Almost-optimal sublinear-time edit distance in the low distance regime. Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos |
| 2022 | An area law for 2d frustration-free spin systems. Anurag Anshu, Itai Arad, David Gosset |
| 2022 | An extendable data structure for incremental stable perfect hashing. Ioana Oriana Bercea, Guy Even |
| 2022 | An improved approximation algorithm for the minimum Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan, Xinzhi Zhang |
| 2022 | Approximate counting and sampling via local central limit theorems. Vishesh Jain, Will Perkins, Ashwin Sah, Mehtaab Sawhney |
| 2022 | Approximate polymorphisms. Gilad Chase, Yuval Filmus, Dor Minzer, Elchanan Mossel, Nitin Saurabh |
| 2022 | Approximately efficient bilateral trade. Yuan Deng, Jieming Mao, Balasubramanian Sivan, Kangning Wang |
| 2022 | Asymptotically good Quantum and locally testable classical LDPC codes. Pavel Panteleev, Gleb Kalachev |
| 2022 | Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster. Emmanuel Abbe, Shuangping Li, Allan Sly |
| 2022 | Breaching the 2-approximation barrier for the forest augmentation problem. Fabrizio Grandoni, Afrouz Jabal Ameli, Vera Traub |
| 2022 | Breaking the Zhiyang He, Jason Li |
| 2022 | Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring. Sepehr Assadi, Pankaj Kumar, Parth Mittal |
| 2022 | Bypassing the surface embedding: approximation schemes for network design in minor-free graphs. Vincent Cohen-Addad |
| 2022 | Byzantine agreement in polynomial time with near-optimal resilience. Shang-En Huang, Seth Pettie, Leqi Zhu |
| 2022 | Circuits resilient to short-circuit errors. Klim Efremenko, Bernhard Haeupler, Yael Tauman Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh R. Saxena |
| 2022 | Clustering mixture models in almost-linear time via list-decodable mean estimation. Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin Tian |
| 2022 | Clustering mixtures with almost optimal separation in polynomial time. Allen Liu, Jerry Li |
| 2022 | Combinatorics via closed orbits: number theoretic Ramanujan graphs are not unique neighbor expanders. Amitay Kamber, Tali Kaufman |
| 2022 | Complexity classification of counting graph homomorphisms modulo a prime number. Andrei A. Bulatov, Amirhossein Kazeminia |
| 2022 | Computational complexity of the ground state energy density problem. James D. Watson, Toby S. Cubitt |
| 2022 | Computational thresholds for the fixed-magnetization Ising model. Charlie Carlson, Ewan Davies, Alexandra Kolla, Will Perkins |
| 2022 | Computing simple mechanisms: Lift-and-round over marginal reduced forms. Yang Cai, Argyris Oikonomou, Mingfei Zhao |
| 2022 | Constant inapproximability for PPA. Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
| 2022 | Counting small induced subgraphs with hereditary properties. Jacob Focke, Marc Roth |
| 2022 | Deniable encryption in a Quantum world. Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani |
| 2022 | Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. Sevag Gharibian, François Le Gall |
| 2022 | Deterministic (1+ Manuela Fischer, Slobodan Mitrovic, Jara Uitto |
| 2022 | Deterministic graph coloring in the streaming model. Sepehr Assadi, Andrew Chen, Glenn Sun |
| 2022 | Deterministic massively parallel connectivity. Sam Coy, Artur Czumaj |
| 2022 | Deterministic, near-linear Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, Allen Xiao |
| 2022 | Directed flow-augmentation. Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström |
| 2022 | Distributed Quantum inner product estimation. Anurag Anshu, Zeph Landau, Yunchao Liu |
| 2022 | Distributed ∆-coloring plays hide-and-seek. Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Dennis Olivetti |
| 2022 | Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, Uri Stemmer |
| 2022 | Dynamic suffix array with polylogarithmic queries and updates. Dominik Kempa, Tomasz Kociumaka |
| 2022 | Edge connectivity augmentation in near-linear time. Ruoxu Cen, Jason Li, Debmalya Panigrahi |
| 2022 | Edge sampling and graph parameter estimation via vertex neighborhood accesses. Jakub Tetek, Mikkel Thorup |
| 2022 | Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. Samuel B. Hopkins, Gautam Kamath, Mahbod Majid |
| 2022 | Entropic independence: optimal mixing of down-up random walks. Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, Thuy-Duong Vuong |
| 2022 | Expanders via local edge flips in quasilinear time. George Giakkoupis |
| 2022 | Explainable Konstantin Makarychev, Liren Shan |
| 2022 | Explicit binary tree codes with sub-logarithmic size alphabet. Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz |
| 2022 | Extractors for sum of two sources. Eshan Chattopadhyay, Jyun-Jie Liao |
| 2022 | Fast FPT-approximation of branchwidth. Fedor V. Fomin, Tuukka Korhonen |
| 2022 | Fast rates for nonparametric online learning: from realizability to learning in games. Constantinos Daskalakis, Noah Golowich |
| 2022 | Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra |
| 2022 | Faster maxflow via improved dynamic spectral vertex sparsifiers. Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, Aaron Sidford |
| 2022 | Faster min-plus product for monotone instances. Shucheng Chi, Ran Duan, Tianle Xie, Tianyi Zhang |
| 2022 | Fixed-parameter tractability of graph isomorphism in graphs with an excluded minor. Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh |
| 2022 | Flow time scheduling and prefix Beck-Fiala. Nikhil Bansal, Lars Rohwedder, Ola Svensson |
| 2022 | Hamiltonian complexity in the thermodynamic limit. Dorit Aharonov, Sandy Irani |
| 2022 | Hardness for triangle problems under even more believable hypotheses: reductions from real APSP, real 3SUM, and OV. Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu |
| 2022 | Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond. Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir |
| 2022 | Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality. Bernhard Haeupler, Harald Räcke, Mohsen Ghaffari |
| 2022 | Hypercontractivity on high dimensional expanders. Tom Gur, Noam Lifshitz, Siqi Liu |
| 2022 | Hypercontractivity on high dimensional expanders. Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett |
| 2022 | Ideals, determinants, and straightening: proving and using lower bounds for polynomial ideals. Robert Andrews, Michael A. Forbes |
| 2022 | Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios. Matthias Englert, Nicolaos Matsakis, Pavel Veselý |
| 2022 | Improved approximations for Euclidean Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, Shyam Narayanan |
| 2022 | Improved communication complexity of fault-tolerant consensus. Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski |
| 2022 | Improved iteration complexities for overconstrained Arun Jambulapati, Yang P. Liu, Aaron Sidford |
| 2022 | Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption. Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang |
| 2022 | Kalman filtering with adversarial corruptions. Sitan Chen, Frederic Koehler, Ankur Moitra, Morris Yau |
| 2022 | Learning general halfspaces with general Massart noise under the Gaussian distribution. Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis |
| 2022 | Learning low-degree functions from a logarithmic number of random queries. Alexandros Eskenazis, Paata Ivanisvili |
| 2022 | Linear space streaming lower bounds for approximating CSPs. Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, Santhoshini Velusamy |
| 2022 | List-decodable covariance estimation. Misha Ivkov, Pravesh K. Kothari |
| 2022 | Locality-sensitive orderings and applications to reliable spanners. Arnold Filtser, Hung Le |
| 2022 | Locally testable codes with constant rate, distance, and locality. Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, Shahar Mozes |
| 2022 | Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion. Bart M. P. Jansen, Michal Wlodarczyk |
| 2022 | Low-rank approximation with Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff |
| 2022 | Low-temperature Ising dynamics with random initializations. Reza Gheissari, Alistair Sinclair |
| 2022 | Maintaining exact distances under multiple edge failures. Ran Duan, Hanlin Ren |
| 2022 | Matrix anti-concentration inequalities with applications. Zipei Nie |
| 2022 | Matrix discrepancy from Quantum communication. Samuel B. Hopkins, Prasad Raghavendra, Abhishek Shetty |
| 2022 | Memory bounds for the experts problem. Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou |
| 2022 | Near-optimal Quantum algorithms for multivariate mean estimation. Arjan Cornelissen, Yassine Hamoudi, Sofiène Jerbi |
| 2022 | Near-optimal distributed degree+1 coloring. Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin, Tigran Tonoyan |
| 2022 | Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games. Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, Tuomas Sandholm |
| 2022 | Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel. Merav Parter |
| 2022 | New streaming algorithms for high dimensional EMD and MST. Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten |
| 2022 | No self-concordant barrier interior point method is strongly polynomial. Xavier Allamigeon, Stéphane Gaubert, Nicolas Vandame |
| 2022 | Nonlocal games, compression theorems, and the arithmetical hierarchy. Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen |
| 2022 | On approximability of satisfiable Amey Bhangale, Subhash Khot, Dor Minzer |
| 2022 | On the complexity of CSP-based ideal membership problems. Andrei A. Bulatov, Akbar Rafiey |
| 2022 | On the complexity of dynamic submodular maximization. Xi Chen, Binghui Peng |
| 2022 | On the complexity of two-party differential privacy. Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia |
| 2022 | On the hardness of dominant strategy mechanism design. Shahar Dobzinski, Shiri Ron, Jan Vondrák |
| 2022 | On the optimal time/space tradeoff for hash tables. Michael A. Bender, Martin Farach-Colton, John Kuszmaul, William Kuszmaul, Mingmou Liu |
| 2022 | Online edge coloring via tree recurrences and correlation decay. Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab Sawhney, Jakub Tarnawski |
| 2022 | Optimal oblivious reconfigurable networks. Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Kleinberg, Rachit Agarwal |
| 2022 | Optimal vertex connectivity oracles. Seth Pettie, Thatchaphol Saranurak, Longhui Yin |
| 2022 | Optimizing strongly interacting fermionic Hamiltonians. Matthew B. Hastings, Ryan O'Donnell |
| 2022 | Parallel repetition for all 3-player games over binary alphabet. Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan |
| 2022 | Positive spectrahedra: invariance principles and pseudorandom generators. Srinivasan Arunachalam, Penghui Yao |
| 2022 | Pricing ordered items. Shuchi Chawla, Rojin Rezvan, Yifeng Teng, Christos Tzamos |
| 2022 | Proving as fast as computing: succinct arguments with constant prover overhead. Noga Ron-Zewi, Ron D. Rothblum |
| 2022 | Pseudodeterminism: promises and lowerbounds. Peter Dixon, Aduri Pavan, Jason Vander Woude, N. V. Vinodchandran |
| 2022 | Public-key Quantum money with a classical bank. Omri Shmueli |
| 2022 | Quantum garbled circuits. Zvika Brakerski, Henry Yuen |
| 2022 | Randomized communication and implicit graph representations. Nathaniel Harms, Sebastian Wild, Viktor Zamaraev |
| 2022 | Rate one-third non-malleable codes. Divesh Aggarwal, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Maciej Obremski, Sruthi Sekar |
| 2022 | Reproducibility in learning. Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell |
| 2022 | Robustly learning mixtures of Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala |
| 2022 | Robustness of average-case meta-complexity via pseudorandomness. Rahul Ilango, Hanlin Ren, Rahul Santhanam |
| 2022 | STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 Stefano Leonardi, Anupam Gupta |
| 2022 | Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication. Sébastien Tavenas, Nutan Limaye, Srikanth Srinivasan |
| 2022 | Simple parallel algorithms for single-site dynamics. Hongyang Liu, Yitong Yin |
| 2022 | Sparsified block elimination for directed laplacians. Richard Peng, Zhuoqing Song |
| 2022 | Sublinear time spectral density estimation. Vladimir Braverman, Aditya Krishnan, Christopher Musco |
| 2022 | Subquadratic dynamic path reporting in directed graphs against an adaptive adversary. Adam Karczmarz, Anish Mukherjee, Piotr Sankowski |
| 2022 | Testing thresholds for high-dimensional sparse random geometric graphs. Siqi Liu, Sidhanth Mohanty, Tselil Schramm, Elizabeth Yang |
| 2022 | The approximate degree of DNF and CNF formulas. Alexander A. Sherstov |
| 2022 | The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity. Zhiyuan Fan, Jiatu Li, Tianqi Yang |
| 2022 | The optimal error resilience of interactive communication over binary channels. Meghal Gupta, Rachel Yun Zhang |
| 2022 | The power of multiple choices in online stochastic matching. Zhiyi Huang, Xinkai Shu, Shuyi Yan |
| 2022 | The power of two choices in graphical allocation. Nikhil Bansal, Ohad N. Feldheim |
| 2022 | The query complexity of certification. Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan |
| 2022 | The shortest even cycle problem is tractable. Andreas Björklund, Thore Husfeldt, Petteri Kaski |
| 2022 | Tight dynamic problem lower bounds from generalized BMM and OMv. Ce Jin, Yinzhan Xu |
| 2022 | Towards optimal lower bounds for k-median and k-means coresets. Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn |
| 2022 | Twin-width IV: ordered graphs and matrices. Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk |
| 2022 | Undirected (1+ Václav Rozhon, Christoph Grunau, Bernhard Haeupler, Goran Zuzic, Jason Li |
| 2022 | Uniform approximations for Randomized Hadamard Transforms with applications. Yeshwanth Cherapanamjeri, Jelani Nelson |
| 2022 | Verifying the unseen: interactive proofs for label-invariant distribution properties. Tal Herman, Guy N. Rothblum |
| 2022 | Worst-case to average-case reductions via additive combinatorics. Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar |