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
• Limit theory for 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. Yuval Dagan, Yuval Filmus, H. Hatami, Yaqiao Li, Trading information complexity for error, submitted. [arXiv]
   
   
2. H. Hatami, Kaave Hosseini, Shachar Lovett, Structure of protocols for XOR functions, FOCS 2016. [ECCC]
   
   
3. H. Hatami, Yingjie Qian, Teaching dimension, VC dimension, and critical sets in Latin squares, Journal of Combinatorics, to appear [arXiv]
   
   
4. H. Hatami, Victoria de Quehen, On the additive bases problem in finite fields, Electronic Journal of Combinatorics, to appear [arXiv]
   
   
5. 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]
   
   
6. 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]
   
   
7. H. Hatami, Pooya Hatami, Shachar Lovett, General systems of linear forms: equidistribution and true complexity, Advances in Mathematics 292 (2016), 446--477. [arXiv]
   
   
8. H. Hatami, Svante Janson, Balazs Szegedy, Graph properties, graph limits and entropy, submitted. [arXiv]
   
   
9. H. Hatami, Laszlo Lovasz, Balazs Szegedy, Limits of local-global convergent graph sequences,
   Geometric and Functional Analysis, 24 (2014), no. 1, 269–296. [arXiv]
   
   
10. H. Hatami, Pooya Hatami, James Hirst, Limits of Boolean Functions on F_p^n,
    Electronic Journal of Combinatorics 21(4), (2014). [Download]
    
    
11. H. Hatami, James Hirst, Serguei Norine, The inducibility of blow-up graphs,
    J. Combin. Theory Ser. B 109 (2014), 196–212. [arXiv]
    
    
12. H. Hatami Shachar Lovett, Estimating the distance from testable affine-invariant properties,
    FOCS 2013. [arXiv]
    
    
13. Arnab Bhattacharyya, Eldar Fischer, H. Hatami, Pooya Hatami, Shachar Lovett, Every locally characterized affine-invariant property is testable,
    STOC 2013. [arXiv]
    
    
14. H. Hatami, Serguei Norine, The entropy of random-free graphons and properties,
    Combinatorics Probability and Computing, 22 (2013), no. 4, 517–526. [arXiv]
    
    
15. H. Hatami and Shachar Lovett, Correlation testing for affine invariant properties on F_p^n in the high error regime,
    STOC 2011. [arXiv]
    
    
16. Anil Ada, Omar Fawzi, H. Hatami, Spectral norm of symmetric functions,
    APPROX-RANDOM 2012: 338-349. [arXiv]
    
    
17. 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]
    
    
18. 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]
    
    
19. H. Hatami, A structure theorem for Boolean functions with small total influences,
    Annals of Mathematics, 176 (2012), no. 1, 509–533. [arXiv]
    
    
20. 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]
    
    
21. 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

1. 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]
   
   
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, 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, Nico Spronk, Amenability constants for semilattice algebras,
   Semigroup forum 79(2) (2009), pp. 279-297. [arXiv]
   
   
6. H. Hatami, Michael Molloy, Sharp thresholds for constraint satisfaction problem and graph homomorphisms ,
   Random Structures & Algorithms , 33(3) (2008), pp. 310-332. [arXiv]
   
   
7. 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]
   
   
8. 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]
   
   
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, Pooya Hatami, Perfect dominating sets in the Cartesian products of prime cycles,
    Electronic Journal of Combinatorics 14(8), (2007). [Download]
    
    
13. 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

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, Ruzbeh Tusserkani, On the complexity of the circular chromatic number,
   Journal of Graph Theory. 47(3) (2004) pp. 226-230. [arXiv]
   
   
3. H. Hatami, 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, 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, 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, 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]