| 2022 | Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses. | Brice Huang, Mark Sellke |
| 2022 | Solving SDP Faster: A Robust IPM Framework and Efficient Implementation. | Baihe Huang, Shunhua Jiang, Zhao Song, Runzhou Tao, Ruizhe Zhang |
| 2022 | Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares. | Max Hopkins, Ting-Chun Lin |
| 2022 | Hardness Self-Amplification from Feasible Hard-Core Sets. | Shuichi Hirahara, Nobutaka Shimizu |
| 2022 | NP-Hardness of Learning Programs and Partial MCSP. | Shuichi Hirahara |
| 2022 | Sampling Lovsz local lemma for general constraint satisfaction solutions in near-linear time. | Kun He, Chunyang Wang, Yitong Yin |
| 2022 | The Implicit Graph Conjecture is False. | Hamed Hatami, Pooya Hatami |
| 2022 | On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited. | Johan Hstad, Kilian Risse |
| 2022 | Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. | Jeongwan Haah, Robin Kothari, Ewin Tang |
| 2022 | Punctured Low-Bias Codes Behave Like Random Linear Codes. | Venkatesan Guruswami, Jonathan Mosheiff |
| 2022 | Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures. | Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan |
| 2022 | Simple Hard Instances for Low-Depth Algebraic Proofs. | Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret |
| 2022 | Separations in Proof Complexity and TFNP. | Mika Gs, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao |
| 2022 | Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]. | Shafi Goldwasser, Michael P. Kim, Vinod Vaikuntanathan, Or Zamir |
| 2022 | Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
| 2022 | Algorithms and Barriers in the Symmetric Binary Perceptron Model. | David Gamarnik, Eren C. Kizildag, Will Perkins, Changji Xu |
| 2022 | Low Treewidth Embeddings of Planar and Minor-Free Metrics. | Arnold Filtser, Hung Le |
| 2022 | Binary Codes with Resilience Beyond 1/4 via Interaction. | Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang |
| 2022 | Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. | Pranjal Dutta, Nitin Saxena |
| 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 | Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds. | Manik Dhar, Zeev Dvir |
| 2022 | Rate-1 Non-Interactive Arguments for Batch-NP and Applications. | Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan |
| 2022 | Fooling polynomials using invariant theory | Harm Derksen, Emanuele Viola |
| 2022 | Pure-Circuit: Strong Inapproximability for PPAD. | Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos |
| 2022 | Induced Cycles and Paths Are Harder Than You Think. | Mina Dalirrooyfard, Virginia Vassilevska Williams |