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 . 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]

Students

Lianna Hambardzumyan; PhD, (cosupervised with Prakash Panangaden).
Yingjie Qian; MSc.
Yaqiao Li PhD.
Liana Yepremyan PhD graduated 2016, (cosupervised with Sergey Norin).
James Hirst MSc graduated 2014, Currently a PhD student at the department of applied mathematics, MIT.
Anil Ada PhD graduated 2013, (cosupervised with professor Denis Therien). Currently an assistant teaching professor at the school of Computer Science, Carnegie Mellon University.

Teaching

Current and future teaching:

Comp 360: Algorithm Design (Winter 2018).
Comp 251: Algorithms and Data structures (Fall 2017).

Past Graduate Courses:

Comp 760: Analysis of Boolean functions (Winter 2017).
Comp 760: Communication and information complexity (Winter 2016).
Comp 760: Communication and information complexity (Winter 2015).
Comp 760: Harmonic Analysis of Boolean Functions (Winter 2014).
Comp 760: Additive combinatorics (Fall 2012).
Comp 760: Harmonic Analysis of Boolean Functions (Fall 2011).

Past Undergraduate Courses:

Comp 330: Theory of Computation (Fall 2016).
Comp 360: Algorithm Design (Winter 2016).
Comp 360: Algorithm Design (Fall 2015).
Comp 362: Honours Algorithm Design (Winter 2015).
Comp 250: Introduction to Computer Science (Fall 2014).
Comp 360: Algorithm Design Techniques (Winter 2014).
Comp 360: Algorithm Design Techniques (Fall 2012).
Comp 360: Algorithm Design Techniques (Fall 2011).
Comp 330: Theory of Computation (Fall 2010).
Mat 202: Linear Algebra with Applications (Fall 2009, Princeton University).

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.