| 2022 | 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, Berkeley, CA, USA, January 31 - February 3, 2022 Mark Braverman |
| 2022 | 3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time. Masoud Seddighin, Saeed Seddighin |
| 2022 | A Complete Linear Programming Hierarchy for Linear Codes. Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones |
| 2022 | A Gaussian Fixed Point Random Walk. Yang P. Liu, Ashwin Sah, Mehtaab Sawhney |
| 2022 | A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi |
| 2022 | A Spectral Approach to Polytope Diameter. Hariharan Narayanan, Rikhav Shah, Nikhil Srivastava |
| 2022 | A Unifying Framework for Characterizing and Computing Width Measures. Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon |
| 2022 | A Variant of the VC-Dimension with Applications to Depth-3 Circuits. Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard |
| 2022 | Adaptive Massively Parallel Constant-Round Tree Contraction. MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, Hsin-Hao Su |
| 2022 | Adversarially Robust Coloring for Graph Streams. Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl |
| 2022 | Algebraic Restriction Codes and Their Applications. Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, Maciej Obremski |
| 2022 | Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. Bruno Pasqualotto Cavalar, Zhenjian Lu |
| 2022 | Almost-Orthogonal Bases for Inner Product Polynomials. Chris Jones, Aaron Potechin |
| 2022 | An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. Sepehr Assadi, Vihan Shah |
| 2022 | An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. Anubhav Baweja, Justin Jia, David P. Woodruff |
| 2022 | Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. Lijie Chen, Shuichi Hirahara, Neekon Vafa |
| 2022 | Balanced Allocations with Incomplete Information: The Power of Two Queries. Dimitrios Los, Thomas Sauerwald |
| 2022 | Beating Classical Impossibility of Position Verification. Jiahui Liu, Qipeng Liu, Luowen Qian |
| 2022 | Beating the Folklore Algorithm for Dynamic Matching. Mohammad Roghani, Amin Saberi, David Wajc |
| 2022 | Bounded Indistinguishability for Simple Sources. Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan |
| 2022 | Budget-Smoothed Analysis for Submodular Maximization. Aviad Rubinstein, Junyao Zhao |
| 2022 | Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians. Anurag Anshu, Chinmay Nirkhe |
| 2022 | Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. Boaz Barak, Kunal Marwaha |
| 2022 | Continuous Tasks and the Asynchronous Computability Theorem. Hugo Rincon Galeana, Sergio Rajsbaum, Ulrich Schmid |
| 2022 | Convex Influences. Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2022 | Correlation Detection in Trees for Planted Graph Alignment. Luca Ganassali, Laurent Massoulié, Marc Lelarge |
| 2022 | Correlation-Intractable Hash Functions via Shift-Hiding. Alex Lombardi, Vinod Vaikuntanathan |
| 2022 | Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan |
| 2022 | Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions. Meryem Essaidi, Matheus V. X. Ferreira, S. Matthew Weinberg |
| 2022 | Cursed yet Satisfied Agents. Yiling Chen, Alon Eden, Juntao Wang |
| 2022 | Deterministic Dynamic Matching in Worst-Case Update Time. Peter Kiss |
| 2022 | Distributed Vertex Cover Reconfiguration. Keren Censor-Hillel, Yannic Maus, Shahar Romem Peled, Tigran Tonoyan |
| 2022 | Domain Sparsification of Discrete Distributions Using Entropic Independence. Nima Anari, Michal Derezinski, Thuy-Duong Vuong, Elizabeth Yang |
| 2022 | Double Coverage with Machine-Learned Advice. Alexander Lindermayr, Nicole Megow, Bertrand Simon |
| 2022 | Dynamic Matching Algorithms Under Vertex Updates. Hung Le, Lazar Milenkovic, Shay Solomon, Virginia Vassilevska Williams |
| 2022 | Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two. Gaurav Sinha |
| 2022 | Eliminating Intermediate Measurements Using Pseudorandom Generators. Uma Girish, Ran Raz |
| 2022 | Embeddings and Labeling Schemes for A. Talya Eden, Piotr Indyk, Haike Xu |
| 2022 | Errorless Versus Error-Prone Average-Case Complexity. Shuichi Hirahara, Rahul Santhanam |
| 2022 | Excluding PH Pessiland. Shuichi Hirahara, Rahul Santhanam |
| 2022 | Explicit Abelian Lifts and Quantum LDPC Codes. Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani |
| 2022 | Extremely Deep Proofs. Noah Fleming, Toniann Pitassi, Robert Robere |
| 2022 | FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. Balaram Behera, Edin Husic, Shweta Jain, Tim Roughgarden, C. Seshadhri |
| 2022 | Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. Sílvia Casacuberta, Rasmus Kyng |
| 2022 | Fixed-Parameter Sensitivity Oracles. Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J. A. Gregor Lagodzinski, Martin Schirneck, Simon Wietheger |
| 2022 | Front Matter, Table of Contents, Preface, Conference Organization. |
| 2022 | Geometric Bounds on the Fastest Mixing Markov Chain. Sam Olesker-Taylor, Luca Zanetti |
| 2022 | Improved Decoding of Expander Codes. Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang |
| 2022 | Improved Hardness of BDD and SVP Under Gap-(S)ETH. Huck Bennett, Chris Peikert, Yi Tang |
| 2022 | Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams |
| 2022 | Indistinguishability Obfuscation of Null Quantum Circuits and Applications. James Bartusek, Giulio Malavolta |
| 2022 | Individual Fairness in Advertising Auctions Through Inverse Proportionality. Shuchi Chawla, Meena Jagadeesan |
| 2022 | Interaction-Preserving Compilers for Secure Computation. Nico Döttling, Vipul Goyal, Giulio Malavolta, Justin Raizes |
| 2022 | Interactive Communication in Bilateral Trade. Jieming Mao, Renato Paes Leme, Kangning Wang |
| 2022 | Interactive Proofs for Synthesizing Quantum States and Unitaries. Gregory Rosenthal, Henry Yuen |
| 2022 | Keep That Card in Mind: Card Guessing with Limited Memory. Boaz Menuhin, Moni Naor |
| 2022 | Larger Corner-Free Sets from Combinatorial Degenerations. Matthias Christandl, Omar Fawzi, Hoang Ta, Jeroen Zuiddam |
| 2022 | Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE. Zvika Brakerski, Vinod Vaikuntanathan |
| 2022 | Lifting with Sunflowers. Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang |
| 2022 | Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman |
| 2022 | Local Access to Random Walks. Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld |
| 2022 | Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics. Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhon, Zoltán Vidnyánszky |
| 2022 | Locality-Preserving Hashing for Shifts with Connections to Cryptography. Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, Ohad Klein |
| 2022 | Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. Noah Shutty, Mary Wootters |
| 2022 | Lower Bounds for Symmetric Circuits for the Determinant. Anuj Dawar, Gregory Wilsenach |
| 2022 | Lower Bounds on Stabilizer Rank. Shir Peleg, Ben Lee Volk, Amir Shpilka |
| 2022 | Matroid Secretary Is Equivalent to Contention Resolution. Shaddin Dughmi |
| 2022 | Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. Amey Bhangale, Aleksa Stankovic |
| 2022 | Maximizing Revenue in the Presence of Intermediaries. Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, Andrés Perlroth |
| 2022 | Mechanism Design with Moral Bidders. Shahar Dobzinski, Sigal Oren |
| 2022 | Mixing in Non-Quasirandom Groups. W. T. Gowers, Emanuele Viola |
| 2022 | Mixing of 3-Term Progressions in Quasirandom Groups. Amey Bhangale, Prahladh Harsha, Sourya Roy |
| 2022 | Monotone Complexity of Spanning Tree Polynomial Re-Visited. Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, Partha Mukhopadhyay |
| 2022 | More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks. Yuqing Kong |
| 2022 | Multi-Channel Bayesian Persuasion. Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, Konstantin Zabarnyi |
| 2022 | Multiscale Entropic Regularization for MTS on General Metric Spaces. Farzam Ebrahimnejad, James R. Lee |
| 2022 | Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu. Mojtaba Hosseini, Vijay V. Vazirani |
| 2022 | Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. Shiri Antaki, Quanquan C. Liu, Shay Solomon |
| 2022 | Noisy Boolean Hidden Matching with Applications. Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou |
| 2022 | Nonlinear Repair Schemes of Reed-Solomon Codes. Roni Con, Itzhak Tamo |
| 2022 | Omnipredictors. Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, Udi Wieder |
| 2022 | On Fairness and Stability in Two-Sided Matchings. Gili Karni, Guy N. Rothblum, Gal Yona |
| 2022 | On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. Ronen Shaltiel, Emanuele Viola |
| 2022 | On Polynomially Many Queries to NP or QMA Oracles. Sevag Gharibian, Dorian Rudolph |
| 2022 | On Semi-Algebraic Proofs and Algorithms. Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere |
| 2022 | On the Download Rate of Homomorphic Secret Sharing. Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, Mary Wootters |
| 2022 | On the Existence of Competitive Equilibrium with Chores. Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta |
| 2022 | Online Multivalid Learning: Means, Moments, and Prediction Intervals. Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, Aaron Roth |
| 2022 | Optimal Bounds for Dominating Set in Graph Streams. Sanjeev Khanna, Christian Konrad |
| 2022 | Optimal Deterministic Clock Auctions and Beyond. Giorgos Christodoulou, Vasilis Gkatzelis, Daniel Schoepflin |
| 2022 | Optimal Sub-Gaussian Mean Estimation in Very High Dimensions. Jasper C. H. Lee, Paul Valiant |
| 2022 | PCPs and Instance Compression from a Cryptographic Lens. Liron Bronfman, Ron D. Rothblum |
| 2022 | Polynomial Identity Testing via Evaluation of Rational Functions. Dieter van Melkebeek, Andrew Morgan |
| 2022 | Pre-Constrained Encryption. Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, Giulio Malavolta |
| 2022 | Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha |
| 2022 | Probing to Minimize. Weina Wang, Anupam Gupta, Jalani Williams |
| 2022 | Pseudorandom Self-Reductions for NP-Complete Problems. Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda |
| 2022 | Quantum Distributed Algorithms for Detection of Cliques. Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman |
| 2022 | Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems. François Le Gall, Saeed Seddighin |
| 2022 | Quantum Meets the Minimum Circuit Size Problem. Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang |
| 2022 | Randomness Extraction from Somewhat Dependent Sources. Marshall Ball, Oded Goldreich, Tal Malkin |
| 2022 | Reduction from Non-Unique Games to Boolean Unique Games. Ronen Eldan, Dana Moshkovitz |
| 2022 | Sample-Based Proofs of Proximity. Guy Goldberg, Guy N. Rothblum |
| 2022 | Secret Sharing, Slice Formulas, and Monotone Real Circuits. Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi |
| 2022 | Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani |
| 2022 | Small Circuits Imply Efficient Arthur-Merlin Protocols. Michael Ezra, Ron D. Rothblum |
| 2022 | Small Hazard-Free Transducers. Johannes Bund, Christoph Lenzen, Moti Medina |
| 2022 | Small-Box Cryptography. Yevgeniy Dodis, Harish Karthikeyan, Daniel Wichs |
| 2022 | Smaller ACC0 Circuits for Symmetric Functions. Brynmor Chapman, R. Ryan Williams |
| 2022 | Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. Sepehr Assadi, Chen Wang |
| 2022 | Sublinear-Time Computation in the Presence of Online Erasures. Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma |
| 2022 | Support Recovery in Universal One-Bit Compressed Sensing. Arya Mazumdar, Soumyabrata Pal |
| 2022 | Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras. Gábor Ivanyos, Tushant Mittal, Youming Qiao |
| 2022 | Symmetric Sparse Boolean Matrix Factorization and Applications. Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang |
| 2022 | Testing Distributions of Huge Objects. Oded Goldreich, Dana Ron |
| 2022 | The Importance of the Spectral Gap in Estimating Ground-State Energies. Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman |
| 2022 | The Space Complexity of Sampling. Eshan Chattopadhyay, Jesse Goodman, David Zuckerman |
| 2022 | Time-Traveling Simulators Using Blockchains and Their Applications. Vipul Goyal, Justin Raizes, Pratik Soni |
| 2022 | Uniform Bounds for Scheduling with Job Size Estimates. Ziv Scully, Isaac Grosof, Michael Mitzenmacher |
| 2022 | Uniform Brackets, Containers, and Combinatorial Macbeath Regions. Kunal Dutta, Arijit Ghosh, Shay Moran |
| 2022 | Vertex Fault-Tolerant Emulators. Greg Bodwin, Michael Dinitz, Yasamin Nazari |
| 2022 | What Does Dynamic Optimality Mean in External Memory? Michael A. Bender, Martin Farach-Colton, William Kuszmaul |