Assistant professor at the CSE Department at the Ohio State University.
Office: Dreese Lab 489
E-mail: pooyahat at gmail dot com
I spent two years as a postdoc at UT Austin hosted by David Zuckerman. I also spent two years as a postdoc at DIMACS and at the Institute for Advanced Study. I received my PhD from the Computer Science Department of University of Chicago, where I was lucky to be supervised by Alexander Razborov and Madhur Tulsiani.
Research Interests: Theoretical computer science: Randomness and Pseudorandomness, Communication Complexity, Analysis of Boolean Functions, Additive Combinatorics
Current Students: Pushen Wang, Yuting Fang
My work is supported by NSF grant CCF-1947546
Higher Order Fourier Analysis and Applications,
(with H. Hatami and S. Lovett)
Foundations and Trends in Theoretical Computer Science,
[ Free Plain Version ]
Theory of Unconditional Pseudorandom Generators
(with William Hoza)
NEW! [ ECCC ]
Selected Papers (full list here):
- Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees
(with William M. Hoza, Avishay Tal, Roei Tell)
STOC 2023 [ ECCC ] - Dimension-free Bounds and Structural Results in Communication Complexity
(with Lianna Hambardzumyan, Hamed Hatami)
Israel Journal of Mathematics 2023 [ IJM ] [ ECCC ] - 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 ] - XOR Lemmas for Resilient Functions against Polynomials
(with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett, David Zuckerman)
STOC 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 ] - Pseudorandom Generators from Polarizing Random Walks
(with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett)
CCC 2018 [ ECCC ] [ Presentation at Simons Institute ]
To appear in Theory of Computing’s Special Issue for CCC 2018 - 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 ] - A characterization of functions with vanishing averages over products of disjoint sets,
(with Hamed Hatami and Yaqiao Li)
European Journal of Combinatorics, 2016 [ arXiv ] [ 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 ] - A lower Bound for the length of a Partial Transversal in a Latin Square,
(with Peter W. Shor)
J. Comb. Theory Ser. A 2008 [ Journal ] [ pdf ]
Pooya Hatami 