Monographs
1. Higher Order Fourier Analysis and Applications,
(with H. Hatami and S. Lovett)
Foundations and Trends in Theoretical Computer Science,
Vol. 13: No. 4, pp 247-448
[ Free Plain Version ]
2. Theory of Unconditional Pseudorandom Generators
(with William Hoza)
NEW! [ ECCC ]
Papers
34. Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees
(with William M. Hoza, Avishay Tal, Roei Tell)
STOC 2023 [ ECCC ]
33. Dimension-free Bounds and Structural Results in Communication Complexity
(with Lianna Hambardzumyan, Hamed Hatami)
Israel Journal of Mathematics 2022 [ IJM ] [ ECCC ]
32. Lower Bound Methods for Sign-rank and their Limitations
(with Hamed Hatami, William Pires, Ran Tao, Rosie Zhao)
RANDOM 2022 [ ECCC ]
31. The Implicit Graph Conjecture is False
(with Hamed Hatami)
FOCS 2022 [ arXiv ]
30. A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
(with Lianna Hambardzumyan, Hamed Hatami)
Discrete Applied Mathematics 2022 [ DAM ] [ arXiv ]
29. Fooling Constant-Depth Threshold Circuits
(with William M. Hoza, Avishay Tal, Roei Tell)
FOCS 2021 [ ECCC ]
28. On Multilinear Forms: Bias, Correlation, and Tensor Rank
(with Abhishek Bhrushundi, Prahladh Harsha, Swastik Kopparty, Mrinal Kumar)
Random 2020 [ ECCC]
27. XOR Lemmas for Resilient Functions against Polynomials
(with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett, David Zuckerman)
STOC 2020 [ ECCC ]
26. Log-Seed Pseudorandom Generators via Iterated Restrictions
(with Dean Doron, William M. Hoza)
CCC 2020 [ ECCC ]
25. Tight Bound on the Number of Relevant Variables in a Bounded degree Boolean function
(with John Chiarelli and Michael Saks)
Combinatorica 2020 [ Journal ] [ arXiv ]
24. Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
(with Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, David Zuckerman)
ICALP 2019 [ arXiv ]
23. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas
(with Dean Doron, William Hoza)
CCC 2019 [ ECCC ]
22. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates
(with Eshan Chattopadhyay, Shachar Lovett, Avishay Tal)
ITCS 2018 [ ECCC ]
21. Pseudorandom Generators from Polarizing Random Walks
(with Eshan Chattopadhyay, Kaave Hosseini, Shachar Lovett)
– CCC 2018 [ ECCC ]
– Theory of Computing 2019, CCC’18 Special Issue [ ToC ]
20. Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity,
(with Eshan Chattopadhyay, Omer Reingold, Avishay Tal)
STOC 2018 [ ECCC ]
19. Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius,
(with Madhur Tulsiani)
SODA 2018 [ pdf ] [ In Proceedings ]
18. Pseudorandom Generators for Low-Sensitivity Functions,
(with Avishay Tal )
ITCS 2018 [ ECCC ] [ In Proceedings ]
17. Low-Sensitivity Functions from Unambiguous Certificates,
(with Shalev Ben-David and Avishay Tal)
ITCS 2017 [ ArXiv ]
16. General systems of linear forms: equidistribution and true complexity,
(with Hamed Hatami and Shachar Lovett)
[ Journal ] [ ECCC ] [ Talk Video ]
Advances in Mathematics, 292:446-477, 2016
15. A characterization of functions with vanishing averages over products of disjoint sets,
(with Hamed Hatami and Yaqiao Li)
[ arXiv ] [ Talk Video ]
European Journal of Combinatorics, 56 (2016) 81-93
14. On the structure of quintic polynomials,
[ arXiv ]
RANDOM 2016
13. An Arithmetic Analogue of Fox’s Triangle Removal Argument,
(with S. Sachdeva and M. Tulsiani)
[ OJAC ] [ arXiv ]
Online Journal of Analytic Combinatorics 11 (2016)
12. Algorithmic Regularity for Polynomials and Applications,
(with A. Bhattacharyya and M. Tulsiani)
[ In Proceedings ], [ arXiv ]
SODA 2015
11. Limits of Boolean Functions on F_p^n,
(with H. Hatami and J. Hirst)
[ EJC ] [ arXiv ]
Electronic Journal of Combinatorics, Vol. 21 (2014) N.4
10. Every locally characterized affine-invariant property is testable,
(with A. Bhattacharyya, E. Fischer, H. Hatami, S. Lovett)
[ ECCC ]
STOC 2013
9. Variations on the Sensitivity Conjecture,
(with Raghav Kulkarni and Denis Pankratov)
[ ToC ]
Theory of Computing Library, Graduate Surveys 4 (2011) 1-27
8. A lower Bound for the length of a Partial Transversal in a Latin Square,
(with Peter W. Shor)
[ pdf ]
J. Comb. Theory Ser. A, 115, 7 (2008) 1103-1113.
7. Distance-Sensitive Property Testing Lower Bounds,
(with J. Brody)
Manuscript [ arXiv ]
6. Perfect dominating sets in the Cartesian products of prime cycles,
(with H. Hatami)
[ EJC ]
Electronic Journal of Combinatorics, Vol. 14,(2007) N8
5. Measure preserving homomorphisms and independent sets in tensor graph powers,
(with B. Behsaz)
[ arXiv ]
Discrete Mathematics. 309, 4 (2009) 955-958.
4. On the signed edge domination number of graphs,
(with S. Akbari, S. Bolouki, M. Siami,)
[ arXiv ]
Discrete Mathematics. 309, 3 (2009) 587-594.
3. On minimum vertex cover of generalized Petersen graphs,
(with M. Behzad and E. S. Mahmoodian)
[ arXiv ]
Bulletin of the ICA. 56 (2009) 98-102.
2. An Approximation Algorithm for the Total Covering Problem,
[ arXiv ]
Discussiones Mathematicae Graph Theory, 27, 3 (2007) 553-560.
1. On minimum vertex covers in generalized Petersen graphs,
(with B. Behsaz and E. S. Mahmoodian)
[ arXiv ]
Australasian Journal of Combinatorics, 40 (2007) 253-264.
Pooya Hatami 