Papers

This page contains some papers produced during the academic year of 2024-2025.

  • Of Dice and Games: A Theory of Generalized Boosting. COLT 2025. N. Brukhim; joint work with Bressan, Cesa-Bianchi, Esposito, Mansour, Moran, Thiessen.
  • A Fine-grained Characterization of PAC Learnability. COLT 2025.  N. Brukhim; joint work with Bressan, Cesa-Bianchi, Esposito, Mansour, Moran, Thiessen.
  • On the Hardness of Bandit Learning. COLT 2025. N. Brukhim; joint work with Pacchiano, Dudik, and Schapire.
  • Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs; Yotam Dikstein, Irit Dinur, Alexander Lubotzky.
  • Chernoff Bounds and Reverse Hypercontractivity on HDX; Yotam Dikstein, Max Hopkins.
  • Sparse High Dimensional Expanders via Local Lifts;Inbar Ben Yaacov, Yotam Dikstein, Gal Maor.
  • Hypercontractivity on HDX II: Symmetrization and q-Norms (STOC 2025); M. Hopkins.
  • The Role of Randomness in Stability (ICML 2025); M. Hopkins.
  • From Generative to Episodic: Sample-Efficient Replicable RL (In Submission); M. Hopkins.
  • Expository Notes: An Introduction to High Dimensional Expanders. M. Hopkins.
  • Z. Kelley, X. Lyu. More efficient sifting for grid norms, and applications to multiparty
    communication complexity. arXiv:2505.01587 [cs.CC], 2025.
  • Yotam Dikstein, Siqi Liu, and Avi Wigderson. Sparser Abelian High Dimensional Expanders, 2025.
  • Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer. On Approximability of Satisfiable k-CSPs: VI. arXiv preprint arXiv:2411.15133, 2024.
  • Amey Bhangale, Subhash Khot, Yang P. Liu, and Dor Minzer. Reasonable Bounds for
    Combinatorial Lines of Length Three. arXiv preprint arXiv:2411.15137, 2024.
  • Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, and Mehtaab Sawhney. Quasipolynomial Bounds for the Corners Theorem. arXiv preprint arXiv:2504.07006, 2025.
  • Arpon Basu, Jun-Ting Hsieh, Andrew Lin, and Peter Manohar. Solving Random
    Planted CSPs Below the nk/2 Threshold. To be submitted to SODA 2026.
  • Elena Grigorescu, Vinayak Kumar, Peter Manohar, and Geoffrey Mon. Linear 3-Query
    Relaxed Locally Decodable Codes Are Locally Decodable. To be submitted to STOC
    2026.
  • Oliver Janzer and Peter Manohar. A kq/q−2 Lower Bound for Odd Query Locally
    Decodable. Codes from Bipartite Kikuchi Graphs. FOCS 2025.
  • Nicholas Kocurek and Peter Manohar. Spectral Refutations of Semirandom k-LIN over Larger Fields. Submitted to APPROX 2025.
  • J. Fox and H. T. Pham, Ruzsa’s conjecture and random Cayley graphs, preprint, 2024+.
    Surprisingly, our proof of the result is largely combinatorial.
  • J. Balogh, A. Bernshteyn, M. Delcourt, A. Ferber and H. T. Pham, Sunflowers in Set
    Systems with Small VC-Dimension, arXiv:2408.04165.
  • R. Nenadov and H. T. Pham, Short proof of the hypergraph container theorem, arXiv:2408.08514.
  • R. Nenadov and H. T. Pham, Spread blow-up lemma with an application to perturbed
    random graphs, arXiv:2410.06132.
  • D. Conlon, J. Fox, H. T. Pham and L. Yepremyan, On the clique number of random
    Cayley graphs and related topics, arXiv:2412.21194.
  • D. Conlon, J. Fox, H. T. Pham and L. Yepremyan, Independence in random graph
    models, preprint, 2025+.
  • N. Alon and H. T. Pham, Sparse random Cayley graphs and random sumsets, preprint,
    2025+.
  • On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials IV. Joint with Joshua A. Grochow. In STOC 2025.
  • On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials V. Joint with Joshua A. Grochow, Katherine E. Stange, and Xiaorui Sun. In STOC 2025.
  • On average orders of automorphism groups of bilinear maps over finite fields. Joint with Markus Blaser, Yinan Li, and Alexander Rogovskyy. On arXiv; submitted for journal publication in March 2025.
  • O. E., Raz, J. Pach, and J. Solymosi, Erd˝os’s unit distance problem and rigidity, in progress.
  • Y. Jahn and O. E. Raz, Improved bound for the k-variate Elekes–R´onyai theorem, in progress.
  • N. Brukhim, A. Brunner, and O. E. Raz, Erd˝os’s Distinct Distances problem over finite fields, in progress.
  • S. Srivastava, F. Jeronimo, T. Mittal and M. Tulsiani; Explicit Codes Approaching Generalized Singleton Bound using Expanders, STOC 2025.
  • S. Srivastava; joint work with Madhur Tulsiani, List Decoding Expander-Based Codes up to Capacity in Near-Linear Time.
  • R. van Handel; The strong convergence phenomenon (survey), Current Developments in Mathematics 2025, to appear.
  • R. van Handel; Strong convergence of uniformly random permutation representations of surface groups (with M. Magee, D. Puder), submitted. arxiv:2504.08988
  • R. van Handel; A new approach to strong convergence II. The classical ensembles (with C.-F. Chen, J. Garza-Vargas), submitted. arxiv:2412.00593.
  • R. van Handel; Matrix chaos inequalities and chaos of combinatorial type (with A. Bandeira, K. Lucca, P. Nizic-Nikolac) In Proc. 2025 ACM Symposium on Theory of Computing—STOC, to appear. arxiv:2412.18468.
  • P. van Hintum; Preprint: Sharp quantitative stability for the Prekopa-Leindler and Borell-Brascamp-Lieb inequalities. With Alessio Figalli and Marius Tiba. arXiv:2501.04656.
  • P. van Hintum; Additive Bases: Change of Domain. With Boris Bukh and Peter Keevash. arXiv:2409.07442.