Hamed Hatami

I'm an assistant professor at the School of computer science and an associate professor at the department of Mathematics and Statistics at McGill University.

I recieved 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
• Limits of graph sequences
• Analysis of Boolean functions
• Additive Combinatorics

Contact Information

E-mail:

hatami at cs . mcgill . ca

Office:

McConnell Engineering Building, Room 308

Mailing address:

McConnell Engineering Bldg, Room 318
3480 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]
  
  

Publications

1. H. Hatami, Pooya Hatami, Yaqiao Li, A characterazition of functions with vanishing averages over products of disjoint sets, submitted. [arXiv]
   
   
2. Yuval Filmus, H. Hatami, Nathan Keller, Noam Lifshitz, On the sum of the L1 influences of bounded functions, submitted. [arXiv]
   
   
3. H. Hatami, Pooya Hatami, Shachar Lovett, General systems of linear forms: equidistribution and true complexity, submitted. [arXiv]
   
   
4. H. Hatami, Svante Janson, Balazs Szegedy, Graph properties, graph limits and entropy, submitted. [arXiv]
   
   
5. H. Hatami, Laszlo Lovasz, Balazs Szegedy, Limits of local-global convergent graph sequences,
   Geometric and Functional Analysis, 24 (2014), no. 1, 269–296. [arXiv]
   
   
6. H. Hatami, Pooya Hatami, and James Hirst, Limits of Boolean Functions on F_p^n,
   Electronic Journal of Combinatorics 21(4), (2014). [Download]
   
   
7. H. Hatami, James Hirst, Serguei Norine, The inducibility of blow-up graphs,
   J. Combin. Theory Ser. B 109 (2014), 196–212. [arXiv]
   
   
8. H. Hatami and Shachar Lovett, Estimating the distance from testable affine-invariant properties,
   FOCS 2013. [arXiv]
   
   
9. Arnab Bhattacharyya, Eldar Fischer, H. Hatami, Pooya Hatami, Shachar Lovett, Every locally characterized affine-invariant property is testable,
   STOC 2013. [arXiv]
   
   
10. H. Hatami and Serguei Norine, The entropy of random-free graphons and properties,
    Combinatorics Probability and Computing, 22 (2013), no. 4, 517–526. [arXiv]
    
    
11. H. Hatami and Shachar Lovett, Correlation testing for affine invariant properties on F_p^n in the high error regime,
    STOC 2011. [arXiv]
    
    
12. Anil Ada, Omar Fawzi, and H. Hatami, Spectral norm of symmetric functions,
    APPROX-RANDOM 2012: 338-349. [arXiv]
    
    
13. 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]
    
    
14. 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]
    
    
15. H. Hatami, A structure theorem for Boolean functions with small total influences,
    Annals of Mathematics, 176 (2012), no. 1, 509–533. [arXiv]
    
    
16. H. Hatami and 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]
    
    
17. 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]
    
    

Graduate school

1. H. Hatami and 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]
   
   
2. H. Hatami, Graph norms and Sidorenko's conjecture ,
   Israel Journal of Mathematics 175(1) (2010), 125-150. [arXiv]
   
   
3. H. Hatami, Decision trees and influence of variables over product probability spaces,
   Combinatorics Probability and Computing 18 (2009), 357-369. [arXiv]
   
   
4. H. Hatami and Xuding Zhu, The fractional chromatic number of graphs of maximum degree at most three,
   SIAM Journal on Discrete Mathematics 23(4) (2009), 1762-1775.
   
   
5. Mahya Ghandehari, H. Hatami, and Nico Spronk, Amenability constants for semilattice algebras,
   Semigroup forum 79(2) (2009), pp. 279-297. [arXiv]
   
   
6. H. Hatami and Michael Molloy, Sharp thresholds for constraint satisfaction problem and graph homomorphisms ,
   Random Structures & Algorithms , 33(3) (2008), pp. 310-332. [arXiv]
   
   
7. Mahya Ghandehari and 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]
   
   
8. H. Hatami, Avner Magen and 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]
   
   
9. H. Hatami, A remark on Bourgain's distributional inequality on the Fourier spectrum of Boolean functions,
   Online Journal of Analytic Combinatorics 1 (2006). [download]
   
   
10. 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]
    
    
11. 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]
    
    
12. H. Hatami and Pooya Hatami, Perfect dominating sets in the Cartesian products of prime cycles,
    Electronic Journal of Combinatorics 14(8), (2007). [Download]
    
    
13. Peyman Afshani and 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

1. 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]
   
   
2. H. Hatami and Ruzbeh Tusserkani, On the complexity of the circular chromatic number,
   Journal of Graph Theory. 47(3) (2004) pp. 226-230. [arXiv]
   
   
3. H. Hatami and Hossein Maserrat, On the computational complexity of defining sets,
   Journal of Discrete Applied Mathematics .149(1-3) (2005) pp. 101-110. [arXiv]
   
   
4. Mahya Ghandehari, H. Hatami and 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]
   
   
5. Peyman Afshani, H. Hatami and 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]
   
   
6. H. Hatami and 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]