Hamed Hatami
I'm an associate professor at the School of computer science and an associate member at the department of Mathematics and Statistics at McGill University.
I received my PhD from the department of Computer Science, University of Toronto under the supervision of Professors Michael Molloy and Balazs Szegedy. Before joining McGill, I spent a year as a Veblen fellow at the department of Mathematics, Princeton University.
Research Interests
- Analytic methods in Combinatorics and Theoretical Computer Science
- Limit theory for graph sequences
- Analysis of Boolean functions
- Additive Combinatorics
Contact Information
E-mail:
hatami at cs . mcgill . caOffice:
McConnell Engineering Building, Room 308
Mailing address:
McConnell Engineering Bldg, Room 3183480 University Montreal, Qc, Canada, H3A 0E9
Selected Publications
- H. Hatami, A structure theorem for Boolean functions with small total influences, Annals of Mathematics, 176 (2012), no. 1, 509–533.
[arXiv]
- H. Hatami and Serguei Norine,
Undecidability of linear inequalities in graph homomorphism densities,
Journal of the American Mathematical Society, 24(2) (2011), 547-565. [arXiv]
Students
Teaching
Current and future teaching:
Past Graduate Courses:
Past Undergraduate Courses:
Publications
- H. Hatami, Sergey Norin,
On the boundary of the region defined by homomorphism densities,
Journal of Combinatorics, to appear [arXiv] - H. Hatami, Yingjie Qian,
The Unbounded-Error Communication Complexity of symmetric XOR functions,
submitted. [arXiv] - Yuval Filmus, H. 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,
H. Hatami, Yaqiao Li,
Trading information complexity for error,
CCC 2017. [arXiv] - H. Hatami,
Kaave Hosseini,
Shachar Lovett,
Structure of protocols for XOR functions, FOCS 2016.
[ECCC]
- H. Hatami, Yingjie Qian,
Teaching dimension, VC dimension, and critical sets in Latin squares,
Journal of Combinatorics, to appear [arXiv] - H. Hatami, Victoria de Quehen,
On the additive bases problem in finite fields,
Electronic Journal of Combinatorics, to appear [arXiv] - H. 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, H. 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] - H. Hatami,
Pooya Hatami,
Shachar Lovett,
General systems of linear forms: equidistribution and true complexity,
Advances in Mathematics 292 (2016), 446--477. [arXiv] - H. Hatami, Svante Janson, Balazs Szegedy,
Graph properties, graph limits and entropy,
Journal of Graph Theory. [arXiv] - H. Hatami, Laszlo Lovasz, Balazs Szegedy,
Limits of local-global convergent graph sequences,
Geometric and Functional Analysis, 24 (2014), no. 1, 269–296. [arXiv] - H. Hatami, Pooya Hatami, James Hirst,
Limits of Boolean Functions on F_p^n,
Electronic Journal of Combinatorics 21(4), (2014). [Download] - H. Hatami, James Hirst,
Serguei Norine,
The inducibility of blow-up graphs,
J. Combin. Theory Ser. B 109 (2014), 196–212. [arXiv] - H. Hatami Shachar Lovett,
Estimating the distance from testable affine-invariant properties,
FOCS 2013. [arXiv] - Arnab Bhattacharyya,
Eldar Fischer,
H. Hatami,
Pooya Hatami,
Shachar Lovett,
Every locally characterized affine-invariant property is testable,
STOC 2013. [arXiv] - H. Hatami, Serguei Norine,
The entropy of random-free graphons and properties,
Combinatorics Probability and Computing, 22 (2013), no. 4, 517–526. [arXiv] - H. Hatami and Shachar Lovett,
Correlation testing for affine invariant properties on F_p^n in the high error regime,
STOC 2011. [arXiv] - Anil Ada, Omar Fawzi, H. Hatami,
Spectral norm of symmetric functions,
APPROX-RANDOM 2012: 338-349. [arXiv] - H. Hatami, Jan Hladky,
Daniel Kral,
Serguei Norine,
Alexander Razborov,
On the number of pentagons in triangle-free graphs,
J. Combin. Theory Ser. A, 120 (2013), no. 3, 722-732. [arXiv] - H. 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] - H. Hatami, A structure theorem for Boolean functions with small total influences,
Annals of Mathematics, 176 (2012), no. 1, 509–533. [arXiv] - H. Hatami, Shachar Lovett, Higher-order Fourier analysis of F_p^n and the complexity of systems of linear forms,
Geometric and Functional Analysis, 21 (2011), no. 6, 1331–1357. [arXiv] - H. Hatami, Serguei Norine,
Undecidability of linear inequalities in graph homomorphism densities,
Journal of the American Mathematical Society, 24(2) (2011), 547-565. [arXiv]
Graduate school
- H. 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] - H. Hatami, Graph norms and Sidorenko's conjecture ,
Israel Journal of Mathematics 175(1) (2010), 125-150. [arXiv] - H. Hatami, Decision trees and influence of variables over product probability spaces,
Combinatorics Probability and Computing 18 (2009), 357-369. [arXiv]
- H. 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. - Mahya Ghandehari, H. Hatami, Nico Spronk,
Amenability constants for semilattice algebras,
Semigroup forum 79(2) (2009), pp. 279-297. [arXiv] - H. Hatami, Michael Molloy,
Sharp thresholds for constraint satisfaction problem and graph homomorphisms ,
Random Structures & Algorithms , 33(3) (2008), pp. 310-332. [arXiv] - Mahya Ghandehari, H. Hatami,
Fourier analysis and large independent sets in powers of complete graphs,
J. Combin. Theory Ser. B 98(1), (2008), pp. 164-172. [arXiv] - H. Hatami, Avner Magen, Vangelis Markakis,
Integrality gaps of semidefinite programs for Vertex Cover and
relations to $\ell_1$ embeddability of Negative type metrics,
SIAM Journal on Discrete Mathematics, 23(1) (2008/09), pp. 178-194. [arXiv]
- H. Hatami,
A remark on Bourgain's distributional inequality on the Fourier spectrum of Boolean functions,
Online Journal of Analytic Combinatorics 1 (2006). [download] - H. 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]
- H. Hatami, Delta+300 is a bound on the adjacent vertex distinguishing edge chromatic number,
J. Combin. Theory Ser. B 95(2) (2005) pp. 246-256. [arXiv]
- H. Hatami, Pooya Hatami,
Perfect dominating sets in the Cartesian products of prime cycles,
Electronic Journal of Combinatorics 14(8), (2007). [Download] - Peyman Afshani, H. Hatami,
Approximation and inapproximability results for maximum clique of disc graphs in high dimensions,
Information Processing Letters, 105(3), (2008), pp. 83-87. [arXiv]
Undergraduate
- Peyman Afshani, Mahsa Ghandehari, Mahya Ghandehari, H. 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]
- H. Hatami, Ruzbeh Tusserkani, On the complexity
of the circular chromatic number,
Journal of Graph Theory. 47(3) (2004) pp. 226-230. [arXiv]
- H. 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, H. 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, H. 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] - H. 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. [arXiv]
Resume
Click here to download please.