Associate professor
CSE at Ohio State University
Office: Dreese Lab 489     E-mail: pooyahat at gmail dot com

---

Research Interests: Theoretical computer science: Randomness and Pseudorandomness, Communication Complexity, Analysis of Boolean Functions, Additive Combinatorics, Learning Theory

Students:
Pushen Wang (CSE)
Yuting Fang (CSE)
Chavdar Lalov (Math)
Sivan Tretiak (Math)

Service:

Program Committee: SODA 2024, FOCS 2025, FOCS 2026
Budget chair at Computational Complexity Foundation (2025-28)

---

Recent Papers (full list here): 

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
(with Ari Blondal, Hamed Hatami, Chavdar Lalov, Sivan Tretiak)
Preprint [ arXiv ]

Simplicial covering dimension of extremal concept classes
(with Ari Blondal, Hamed Hatami, Chavdar Lalov, Sivan Tretiak)
ITCS 2026 [ arXiv ]

Stability and List-Replicability for Agnostic Learners
(with Ari Blondal, Shan Gao, H. Hatami)
COLT 2025 [ arXiv ]

Constant-Cost Communication is not Reducible to k-Hamming Distance
(with Yuting Fang, Nathan Harms, Mika Göös)
STOC 2025  [ arXiv ]

---

Selected Surveys (full list here)

Paradigms for Unconditional Pseudorandom Generators
(with William M. Hoza)
Foundations and Trends in Theoretical Computer Science [ 📘 FnTTCS purchase link ] [ Old version: ECCC ]

Higher Order Fourier Analysis and Applications,
(with H. Hatami and S. Lovett)
Foundations and Trends in Theoretical Computer Science [ 📘 FnTTCS purchase link ] [ Free Plain Version ]

---

Selected Papers (full list here): 

Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces
(with Ari Blondal, Hamed Hatami, Chavdar Lalov, Sivan Tretiak)
[ arXiv ]

Constant-Cost Communication is not Reducible to k-Hamming Distance
(with Yuting Fang, Nathan Harms, Mika Göös)
STOC 2025  [ arXiv ]

Online Learning and Disambiguations of Partial Concept Classes
(with Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini)
ICALP 2023 (Best Paper) [ arXiv ]

The Implicit Graph Conjecture is False
(with Hamed Hatami)
FOCS 2022 [ arXiv ]

Fooling Constant-Depth Threshold Circuits
(with William M. Hoza, Avishay Tal, Roei Tell)
FOCS 2021 [ ECCC ] [ TCS+ presentation by William Hoza ]

Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function
(with John Chiarelli and Michael Saks)
Combinatorica 2020 [ Journal ] [ arXiv ]

Pseudorandom Generators from Polarizing Random Walks
(with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett)
CCC 2018 [ ECCC ] [ Presentation at Simons Institute ] 
Theory of Computing 2019 [ToC]

Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity,
(with Eshan Chattopadhyay, Omer Reingold, Avishay Tal)
STOC 2018 [ ECCC ] [ Presentation at IAS by Eshan Chattopadhyay ]

General systems of linear forms: equidistribution and true complexity,
(with Hamed Hatami and Shachar Lovett)
Advances in Mathematics, 2016  [ Journal ] [ ECCC ] [ Presentation at IAS ]

Every locally characterized affine-invariant property is testable,
(with A. Bhattacharyya, E. Fischer, H. Hatami, S. Lovett)
STOC 2013 [ ECCC ] [ Presentation at Simons Institute by Hamed Hatami ]

---

My work has been supported by NSF grant CCF-1947546