All Publications
2026
- [arXiv] Csongor Beke, Marcel K. Goh, Hamed Hatami, Sean Jaffe, Daniel Naylor, A characterization of idempotent Schur multipliers,
- [arXiv] Marcel K. Goh, Hamed Hatami, Communication complexity of point-line incidences over the reals,
- [arXiv] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak, Sign-Rank, Index, and List Replicability: Connections and Separations,
- [arXiv] Riju Bindua, Hamed Hatami, Hasti Karimi, Robert Robere, Lower Bounds for Approximate Sign Rank,
- [arXiv] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak, Tight list replicability bounds via a novel sphere covering theorem,
COLT 2026 - [arXiv] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak, Borsuk-Ulam and Replicable Learning of Large-Margin Halfspaces,
STOC 2026 - [arXiv] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak, Simplicial covering dimension of extremal concept classes,
ITCS 2026 - [ECCC] Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley, A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications,
Algorithmica + ITCS 2025, 88, article number 54 (2026)
2025
- [arXiv] Marcel K. Goh, Hamed Hatami, Block complexity and idempotent Schur multipliers,
International Mathematics Research Notices (accepted) - [arXiv] Marcel K. Goh, Hamed Hatami, Block structure in boolean matrices of bounded factorization norm,
Submitted - [arXiv] Ari Blondal, Shan Gao, Hamed Hatami, Pooya Hatami, Stability and List-Replicability for Agnostic Learners,
COLT 2025 - [arXiv] Nader H. Bshouty, Tsun-Ming Cheung, Gergely Harcos, Hamed Hatami, Anthony Ostuni, A tight lower bound on non-adaptive group testing estimation,
Discrete Appl. Math. 336 (2025), 1–15. - [ECCC] Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley, Separation of the factorization norm and randomized communication complexity,
Computational Complexity + CCC 2023
2024
- [arXiv] Yuval Filmus, Esty Kelman, Hamed Hatami, Kaave Hosseini, Sparse graph counting and Kelley-Meka bounds for binary systems,
FOCS 2024 - [arXiv] Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein, Boolean functions with small approximate spectral norm,
Discrete Analysis, (2024) - [ECCC] Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha Sareeni, Discrepancy and communication complexity of halfplanes,
SoCG 2024 - [arXiv] Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni, Refuting approaches to the log-rank conjecture for XOR functions,
ICALP 2024 - [arXiv] Stefan Grosser, Hamed Hatami, Peter Nelson, Sergey Norin, Typical structure of hereditary properties of binary matroids,
J. Combin. Theory Ser. B, 167 (2024) 283-302
2023
- [arXiv] Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami, Kaave Hosseini, Online Learning and Disambiguations of Partial Concept Classes,
ICALP 2023 (Best Paper Award) - [ECCC] Hamed Hatami, Kaave Hosseini, Xiang Ming, A Borsuk-Ulam lower bound for sign-rank and its applications,
STOC 2023
2022
- [arXiv] Hamed Hatami and Pooya Hatami, The Implicit Graph Conjecture is False,
FOCS 2022 - [ECCC] Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, Dimension-free Bounds and Structural Results in Communication Complexity,
Israel Journal of Mathematics (2022). - [ECCC] Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao, Lower bound methods for sign-rank and their limitations,
APPROX-RANDOM 2022 - [ECCC] Hamed Hatami, Kaave Hosseini, Shachar Lovett, Sign rank vs Discrepancy,
Theory of Computing + CCC 2020 - [arXiv] Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, A counter-example to the probabilistic universal graph conjecture via randomized communication complexity,
Discrete Appl. Math. 322 (2022), 117–122. - [ECCC] Ben Davis, Hamed Hatami, Ran Tao, William Pires, Hamza Usmani, On public-coin zero-error randomized communication complexity,
Information Processing Letters (2022)
2021
- [arXiv] Noah Brustle, Tal Elbaz, Hamed Hatami, Onur Kocer, Bingchan Ma, Approximation algorithms for hitting subgraphs,
IWOCA 2021
2020
- [arXiv] Lianna Hambardzumyan, Hamed Hatami, Yingjie Qian, Lower bounds for graph bootstrap percolation via properties of polynomials,
J. Combin. Theory Ser. A, 174 (2020), 105--253.
2019
- [ECCC] Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman, Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions,
ICALP 2019 - [arXiv] Hamed Hatami, Sergey Norin, On the boundary of the region defined by homomorphism densities,
Journal of Combinatorics, 10 (2019), no. 2, 203--219.
2018
- [arXiv] Hamed Hatami, Svante Janson, Balazs Szegedy, Graph properties, graph limits and entropy,
Journal of Graph Theory. 87 (2018), no. 2, 208--229. - [arXiv] Hamed Hatami, Yingjie Qian, Teaching dimension, VC dimension, and critical sets in Latin squares,
Journal of Combinatorics, 9 (2018), no. 1, 9--20. - [arXiv] Hamed Hatami, Yingjie Qian, The Unbounded-Error Communication Complexity of symmetric XOR functions,
submitted.
2017
- [arXiv] Yuval Filmus, Hamed Hatami, Yaqiao Li, Suzin You, Information complexity of the AND function in the two-party and multi-party settings,
COCOON 2017 - [arXiv] Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li, Trading information complexity for error,
CCC 2017
2016
- [ECCC] Hamed Hatami, Kaave Hosseini, Shachar Lovett, Structure of protocols for XOR functions,
FOCS 2016 - [arXiv] Hamed Hatami, Victoria de Quehen, On the additive bases problem in finite fields,
Electronic Journal of Combinatorics, 23 (2016), no. 3, Paper 3.33. - [arXiv] Hamed Hatami, Pooya Hatami, Yaqiao Li, A characterization of functions with vanishing averages over products of disjoint sets,
European J. Combin. 56 (2016), 81--93. - [arXiv] Yuval Filmus, Hamed Hatami, Nathan Keller, Noam Lifshitz, On the sum of the L1 influences of bounded functions,
Israel Journal of Mathematics. (2016), no. 1, 167--192. - [arXiv] Hamed Hatami, Pooya Hatami, Shachar Lovett, General systems of linear forms: equidistribution and true complexity,
Advances in Mathematics 292 (2016), 446--477.
2014
- [arXiv] Hamed Hatami, Laszlo Lovasz, Balazs Szegedy, Limits of local-global convergent graph sequences,
Geometric and Functional Analysis, 24 (2014), no. 1, 269–296. - [arXiv] Hamed Hatami, James Hirst, Sergey Norin, The inducibility of blow-up graphs,
J. Combin. Theory Ser. B 109 (2014), 196–212.
2013
- [arXiv] Hamed Hatami, Shachar Lovett, Estimating the distance from testable affine-invariant properties,
FOCS 2013 - [arXiv] Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett, Every locally characterized affine-invariant property is testable,
STOC 2013 - [arXiv] Hamed Hatami, Sergey Norin, The entropy of random-free graphons and properties,
Combinatorics Probability and Computing, 22 (2013), no. 4, 517–526. - [arXiv] Hamed Hatami, Jan Hladky, Daniel Kral, Sergey Norin, Alexander Razborov, On the number of pentagons in triangle-free graphs,
J. Combin. Theory Ser. A, 120 (2013), no. 3, 722-732.
2012
- [arXiv] Hamed Hatami, A structure theorem for Boolean functions with small total influences,
Annals of Mathematics, 176 (2012), no. 1, 509–533. - [arXiv] Hamed Hatami, Jan Hladky, Daniel Kral, Serguei Norine, Alexander Razborov, Non-three-colorable common graphs exist,
Combinatorics Probability and Computing, 21 (2012), no. 5, 734-742. - [arXiv] Anil Ada, Omar Fawzi, Hamed Hatami, Spectral norm of symmetric functions,
APPROX-RANDOM 2012
2011
- [arXiv] Hamed Hatami, Sergey Norin, Undecidability of linear inequalities in graph homomorphism densities,
Journal of the American Mathematical Society, 24(2) (2011), 547-565. - [arXiv] Hamed Hatami and Shachar Lovett, Correlation testing for affine invariant properties on 𝔽pn in the high error regime,
STOC 2011 - [arXiv] Hamed Hatami, Shachar Lovett, Higher-order Fourier analysis of 𝔽pn and the complexity of systems of linear forms,
Geometric and Functional Analysis, 21 (2011), no. 6, 1331–1357.
MSc and PhD years
- [arXiv] Hamed Hatami, Michael Molloy,The scaling window for a random graph with a given degree sequence,
Random Structures & Algorithms, 41 (2012), no. 1, 99–123.
SODA10. - [arXiv] Hamed Hatami,Graph norms and Sidorenko's conjecture,
Israel Journal of Mathematics 175(1) (2010), 125-150. - [arXiv] Hamed Hatami, Decision trees and influence of variables over product probability spaces,
Combinatorics Probability and Computing 18 (2009), 357-369. - Hamed Hatami, Xuding Zhu, The fractional chromatic number of graphs of maximum degree at most three,
SIAM Journal on Discrete Mathematics 23(4) (2009), 1762-1775. - [arXiv] Mahya Ghandehari, Hamed Hatami, Nico Spronk, Amenability constants for semilattice algebras,
Semigroup forum 79(2) (2009), pp. 279-297. - [arXiv] Hamed Hatami and Michael Molloy,Sharp thresholds for constraint satisfaction problem and graph homomorphisms,
Random Structures & Algorithms, 33(3) (2008), pp. 310-332. - [arXiv] Mahya Ghandehari and Hamed Hatami, Fourier analysis and large independent sets in powers of complete graphs,
J. Combin. Theory Ser. B 98(1), (2008), pp. 164-172. - [arXiv] Hamed Hatami, Avner Magen, Vangelis Markakis, Integrality gaps of semidefinite programs for Vertex Cover and relations to ℓ1 embeddability of Negative type metrics,
SIAM Journal on Discrete Mathematics, 23(1) (2008/09), pp. 178-194. - [download] Hamed Hatami, A remark on Bourgain's distributional inequality on the Fourier spectrum of Boolean functions,
Online Journal of Analytic Combinatorics 1 (2006). - [arXiv] Hamed Hatami, Random cubic graphs are not homomorphic to the cycle of size 7,
J. Combin. Theory Ser. B 93(2) (2005) pp. 319-325. - [arXiv] Hamed Hatami, Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number,
J. Combin. Theory Ser. B 95(2) (2005) pp. 246-256. - [Download] Hamed Hatami, Pooya Hatami, Perfect dominating sets in the Cartesian products of prime cycles,
Electronic Journal of Combinatorics 14(8), (2007). - [arXiv] Peyman Afshani and Hamed Hatami, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions,
Information Processing Letters, 105(3), (2008), pp. 83-87.
Undergrad years
- [arXiv] Peyman Afshani, Mahsa Ghandehari, Mahya Ghandehari, Hamed Hatami, Ruzbeh Tusserkani, Xuding Zhu, Circular chromatic index of graphs of maximum degree 3,
Journal of Graph Theory. 49(4) (2005) pp. 325-335. - [arXiv] Hamed Hatami, Ruzbeh Tusserkani, On the complexity of the circular chromatic number,
Journal of Graph Theory. 47(3) (2004) pp. 226-230. - [arXiv] Hamed Hatami, Hossein Maserrat, On the computational complexity of defining sets,
Journal of Discrete Applied Mathematics.149(1-3) (2005) pp. 101-110. - [arXiv] Mahya Ghandehari, Hamed Hatami, E.S. Mahmoodian,On the size of the minimum critical set of a Latin square,
Journal of Discrete Mathematics. 293(1-3) (2005) pp. 121-127. - [arXiv] Peyman Afshani, Hamed Hatami, E.S. Mahmoodian, On the size of the spectrum of the forced matching number of graphs,
Australasian Journal of Combinatorics, 30 (2004) pp. 147-160. - [arXiv] Hamed Hatami, E.S. Mahmoodian, A lower bound for the size of the largest critical sets in Latin squares,
Bulletin of the Institute of Combinatorics and its Applications (Canada). 38 (2003) pp.19-22.