Papers

  • Learning Conditional Averages. COLT 2026. Nataly Brukhim, joint work with Bressan, Cesa-Bianchi, Esposito, Mansour, Moran, Thiessen.
  • Lookahead identification in adversarial bandits: accuracy and memory bounds.  Nataly Brukhim, joint work with Ciliberto, Cesa-Bianchi.
  • The Distinct Distances Problem over Finite Fields. Nataly Brukhim. Joint work with Brunner, Raz.
  • L. Bowen, M. Chapman, Surjunctivity does not characterize cosoficity of invariant random subgroups, 
    preprint (2025). Arxiv: https://arxiv.org/abs/2511.06586.
  • M. Chapman, I. Dinur, D. Puder, Derandomization of Homomorphism Testers and Stability of Groups, ongoing project.
  • High Rate Efficient Local List Decoding from HDX. Authors: Yotam Dikstein, Max Hopkins, Russell 
    Impagliazzo, Toniann Pitassi. Appeared in STOC 2026. arxiv:2601.22535 (proceedings not yet available).
  • M. Hopkins, High Rate Efficient Local List Decoding from HDX (STOC 2026).
  • M. Hopkins, A Simple Sub-Polynomial Degree  Coboundary Expander (CCC 2026).
  • M. Hopkins, Toward a KKL Theorem for any HDX (RANDOM 2026).
  • M. Hopkins, Approximate Replicability in Learning (In Submission).
  • M. Hopkins, Non-signaling locality lower bounds for dominating set (In Submission).
  • Rahul Ilango, “Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No 
    Interaction, No Setup, and Perfect Soundness,” FOCS 2025. IACR ePrint 2025/1296, ECCC TR25-095.  (Co-winner of the Machtey Award for Best Student Paper.)
  • Shuichi Hirahara and Rahul Ilango, “NP-Hardness of the Minimum Circuit Size Problem from 
    Well-Studied Assumptions,” FOCS 2025.
  • Rahul Ilango and Alex Lombardi, “Cryptography Meets Worst-Case Complexity: Optimal Security and  More from iO and Worst-Case Assumptions,” FOCS 2025. IACR ePrint 2025/1087, ECCC TR25-072.
  • Rahul Ilango, “The Oracle Derandomization Hypothesis is False (And More) Assuming No Natural Proofs,” 2025. ECCC TR25-190.
  • Z. Kelley and X. Lyu, “More Efficient Sifting for Grid Norms, and Applications to Multi-party  Communication Complexity.” Published in the IEEE Symposium on Foundations of Computer Science (FOCS) 2025. arXiv:2505.01587.
  • Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations; Authors: Elena Grigorescu, Vinayak Kumar, Peter Manohar, Geoffrey Mon Published in the Symposium on the Theory of Computation (STOC) 2026. Available on arXiv at https://arxiv.org/pdf/2511.02633
  • Solving Random Planted CSPs Below the nᵏ/² Threshold; Authors: Arpon Basu, Jun-Ting Hsieh, Andrew Lin, Peter Manohar, Published in the International Colloquium on Automata, Languages and Programming (ICALP) 2026. Available on arXiv at https://arxiv.org/pdf/2507.10833
  • Preprint: Aldous-type spectral gaps in unitary groups: Doron Puder and Gil Alon (Open U, Israel), under review in Journal of the European Mathematical. Preprint is available at https://arxiv.org/abs/2603.00353.
  • Aldous-type spectral gaps in generalized symmetric groups: Doron Puder and Niv Levhari; under review in Annales de l’Institut Henri Poincare. Preprint available at https://arxiv.org/abs/2605.22101.
  • Preprint: Stable invariants of words from random matrices; Doron Puder and Yotam Shomroni; under review in Forum of Mathematics: Sigma. Preprint available at https://arxiv.org/abs/2311.17733.
  • Preprint: Stable invariants of words from random matrices II: formulas and extensions; Doron Puder and Yotam Shomroni; under review in Algebraic Combinatorics. Preprint available at https://arxiv.org/abs/2509.17271.
  • Near-Maximum Circuit Lower Bounds for Exponential Time with Merlin-Arthur Queries, Hanlin Ren and Ryan Williams. Submitted to FOCS 2026.
  • Many Proof Complexity Generators Inside One Demi-Bits Generator, Hanlin Ren with Xin Li and Yan Zhong. Submitted to FOCS 2026.
  • M. Sankar, Codegree Turán Densities of Tight Cycles (arXiv:2602.18398, joint with Jozsef Balogh and Haoran Luo.
  • Ryan Williams. Simulating Fast Algorithms With Less Memory. Bulletin of the EATCS. 147:60–71, October 2025.
  • Neha Pant and Ryan Williams. Beating trivial time for tricky triangle tasks. Submitted to ICALP, 2026.
  • Lijie Chen, Jiatu Li, Igor Oliveira, and Ryan Williams. A Theory for Probabilistic Polynomial-Time Reasoning. To appear in STOC, 2026.
  • No Exponential Quantum Speedup for SIS∞ Anymore Robin Kothari, Ryan O’Donnell, Kewen Wu
    Published at Symposium on Theory of Computing (STOC), 2026. arXiv: https://arxiv.org/abs/2510.07515.
  • Preprint: Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu; Accepted at Quantum Information Processing (QIP), 2026. Published at Innovations in Theoretical Computer Science Conference (ITCS), 2026. DOI: https://doi.org/10.4230/LIPIcs.ITCS.2026.73, arXiv: https://arxiv.org/abs/2510.07808.
  • Preprint:  QAC⁰ Contains TC⁰ (with Many Copies of the Input); Daniel Grier, Jackson Morris, Kewen Wu; arXiv: https://arxiv.org/abs/2601.03243.
  • Preprint: Symmetric Distributions from Shallow Circuits Daniel Kane, Anthony Ostuni, Kewen Wu; arXiv: https://arxiv.org/abs/2511.14127.