Pooya Hatami

Associate Professor
Department of Computer Science and Engineering
The Ohio State University

Office: Dreese Lab 489
Email: pooyahat at gmail dot com

Teaching | Google Scholar

Research interests

Theoretical computer science, pseudorandomness, communication complexity, analysis of Boolean functions, learning theory, and additive combinatorics.

Students

• Pushen Wang
• Yuting Fang
• Chavdar Lalov (co-advised with Yifan Jing)
• Sivan Tretiak (co-advised with Maria Han Veiga)

Service

Program committees: SODA 2024, FOCS 2025, FOCS 2026.
Budget Chair, Computational Complexity Foundation, 2025–2028.

Monographs and surveys

• Structure in Communication Complexity and Constant-Cost Complexity Classes. with Hamed Hatami.
  Invited survey article for ACM SIGACT News Complexity Theory Column. [SIGACT] [ECCC] [arXiv]
• Paradigms for Unconditional Pseudorandom Generators.
  with William M. Hoza.
  Foundations and Trends in Theoretical Computer Science. [FnTTCS] [old version]
• Higher Order Fourier Analysis and Applications.
  with Hamed Hatami and Shachar Lovett.
  Foundations and Trends in Theoretical Computer Science, Vol. 13, No. 4, pp. 247--448. [FnTTCS] [free plain version]
• Variations on the Sensitivity Conjecture.
  with Raghav Kulkarni and Denis Pankratov.
  Theory of Computing Library, Graduate Surveys 4 (2011), 1--27. [ToC]

Papers

• Exponential Correlation Bounds for Polynomials.
  with Eshan Chattopadhyay, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola.
  preprint. [ECCC] [arXiv] [Substantial AI assistance]
• A polylogarithmic bound for list replicability.
  with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  preprint. [arXiv] [Substantial AI assistance]
• Sign-Rank, Index, and List Replicability: Connections and Separations.
  with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  preprint. [arXiv]
• Tight list replicability bounds via a novel sphere covering theorem.
  with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  COLT 2026. [arXiv]
• Simplicial covering dimension of extremal concept classes.
  with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  ITCS 2026. [arXiv]
• Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces.
  with Ari Blondal, Hamed Hatami, Chavdar Lalov, and Sivan Tretiak.
  STOC 2026. [arXiv]
• Stability and List-Replicability for Agnostic Learners.
  with Ari Blondal, Shan Gao, and Hamed Hatami.
  COLT 2025. [arXiv]
• Constant-Cost Communication is not Reducible to k-Hamming Distance.
  with Yuting Fang, Nathan Harms, and Mika Göös.
  STOC 2025. [arXiv]
• Hilbert Functions and Low-Degree Randomness Extractors.
  with Alexander Golovnev, Zeyu Guo, Satyajeet Nagargoje, and Chao Yan.
  RANDOM 2024. [arXiv] [ECCC]
• No Complete Problem for Constant-Cost Randomized Communication.
  with Yuting Fang, Lianna Hambardzumyan, and Nathan Harms.
  STOC 2024. [conference version] [arXiv]
• Online Learning and Disambiguations of Partial Concept Classes.
  with Tsun-Ming Cheung, Hamed Hatami, and Kaave Hosseini.
  ICALP 2023. Best Paper. [arXiv]
• Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees.
  with William M. Hoza, Avishay Tal, and Roei Tell.
  STOC 2023. [ECCC]
• Dimension-free Bounds and Structural Results in Communication Complexity.
  with Lianna Hambardzumyan and Hamed Hatami.
  Israel Journal of Mathematics, 2023. [IJM] [ECCC]
• The Implicit Graph Conjecture is False.
  with Hamed Hatami.
  FOCS 2022. [arXiv]
• Lower Bound Methods for Sign-rank and their Limitations.
  with Hamed Hatami, William Pires, Ran Tao, and Rosie Zhao.
  RANDOM 2022. [ECCC]
• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity.
  with Lianna Hambardzumyan and Hamed Hatami.
  Discrete Applied Mathematics, 2022. [DAM] [arXiv]
• Fooling Constant-Depth Threshold Circuits.
  with William M. Hoza, Avishay Tal, and Roei Tell.
  FOCS 2021. [ECCC]
• On Multilinear Forms: Bias, Correlation, and Tensor Rank.
  with Abhishek Bhrushundi, Prahladh Harsha, Swastik Kopparty, and Mrinal Kumar.
  RANDOM 2020. [arXiv]
• XOR Lemmas for Resilient Functions against Polynomials.
  with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett, and David Zuckerman.
  STOC 2020. [ECCC]
• Log-Seed Pseudorandom Generators via Iterated Restrictions.
  with Dean Doron and William M. Hoza.
  CCC 2020. [ECCC]
• Tight Bound on the Number of Relevant Variables in a Bounded Degree Boolean Function.
  with John Chiarelli and Michael Saks.
  Combinatorica, 2020. [journal] [arXiv]
• Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions.
  with Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, and David Zuckerman.
  ICALP 2019. [arXiv]
• Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas.
  with Dean Doron and William Hoza.
  CCC 2019. [ECCC]
• Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.
  with Eshan Chattopadhyay, Shachar Lovett, and Avishay Tal.
  ITCS 2018. [ECCC]
• Pseudorandom Generators from Polarizing Random Walks.
  with Eshan Chattopadhyay, Kaave Hosseini, and Shachar Lovett.
  CCC 2018; Theory of Computing 2019, CCC'18 Special Issue. [ECCC] [ToC]
• Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity.
  with Eshan Chattopadhyay, Omer Reingold, and Avishay Tal.
  STOC 2018. [ECCC]
• Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius.
  with Madhur Tulsiani.
  SODA 2018. [pdf] [proceedings]
• Pseudorandom Generators for Low-Sensitivity Functions.
  with Avishay Tal.
  ITCS 2018. [ECCC] [proceedings]
• Low-Sensitivity Functions from Unambiguous Certificates.
  with Shalev Ben-David and Avishay Tal.
  ITCS 2017. [arXiv]
• General systems of linear forms: equidistribution and true complexity.
  with Hamed Hatami and Shachar Lovett.
  Advances in Mathematics, 292:446--477, 2016. [journal] [ECCC] [talk video]
• A characterization of functions with vanishing averages over products of disjoint sets.
  with Hamed Hatami and Yaqiao Li.
  European Journal of Combinatorics, 56 (2016), 81--93. [arXiv] [talk video]
• On the structure of quintic polynomials.
  RANDOM 2016. [arXiv]
• An Arithmetic Analogue of Fox's Triangle Removal Argument.
  with Sushant Sachdeva and Madhur Tulsiani.
  Online Journal of Analytic Combinatorics 11 (2016). [OJAC] [arXiv]
• Algorithmic Regularity for Polynomials and Applications.
  with Arnab Bhattacharyya and Madhur Tulsiani.
  SODA 2015. [proceedings] [arXiv]
• Every locally characterized affine-invariant property is testable.
  with Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, and Shachar Lovett.
  STOC 2013. [ECCC] [arXiv]
• Variations on the Sensitivity Conjecture.
  with Raghav Kulkarni and Denis Pankratov.
  Theory of Computing Library, Graduate Surveys 4 (2011), 1--27. [ToC]
• A lower Bound for the length of a Partial Transversal in a Latin Square.
  with Peter W. Shor.
  Journal of Combinatorial Theory, Series A, 115, 7 (2008), 1103--1113. [doi]
• Distance-Sensitive Property Testing Lower Bounds.
  with Joshua Brody.
  Manuscript. [arXiv]
• Perfect dominating sets in the Cartesian products of prime cycles.
  with Hamed Hatami.
  Electronic Journal of Combinatorics, Vol. 14 (2007), N8. [EJC]
• Measure preserving homomorphisms and independent sets in tensor graph powers.
  with Babak Behsaz.
  Discrete Mathematics, 309, 4 (2009), 955--958. [arXiv]
• On the signed edge domination number of graphs.
  with Saeed Akbari, Sadegh Bolouki, and Milad Siami.
  Discrete Mathematics, 309, 3 (2009), 587--594. [arXiv]
• On minimum vertex cover of generalized Petersen graphs.
  with Mehdi Behzad and E. S. Mahmoodian.
  Bulletin of the ICA, 56 (2009), 98--102. [ICA]
• An Approximation Algorithm for the Total Covering Problem.
  Discussiones Mathematicae Graph Theory, 27, 3 (2007), 553--560. [arXiv]
• On minimum vertex covers in generalized Petersen graphs.
  with Babak Behsaz and E. S. Mahmoodian.
  Australasian Journal of Combinatorics, 40 (2007), 253--264. [arXiv]