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 was a Veblen fellow at the Institute for Advanced Studies, and the Department of Mathematics, Princeton University.

My research interests are in Theoretical Computer Science and Pure Mathematics:

• Communication complexity;
• Analytic methods in combinatorics and theoretical Computer Science;
• Fourier analysis of Boolean functions;
• Additive combinatorics.

Teaching and pedagogical matters:

• Comp 760 (Fall 2024): Analysis of Boolean Functions.
  
• Comp 360 (Winter 2024): Algorithm Design.
  
• Comp 362 (Winter 2024):: Honours Algorithm Design.
  
• Past courses and lecture notes.
  
• Summer Research: independent or official such as NSERC-USRA, SURA, Comp 396, Comp 400.
  
• Requesting a Recommendation Letter.

Publications:

• Click here for All Publications.
  
  
  
• Selected Publications in Theoretical Computer Science:
  
  
  • (Best Paper Award) Tsun-Ming Cheung, H. Hatami, Pooya Hatami, Kaave Hosseini, Online Learning and Disambiguations of Partial Concept Classes,
    50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023). [ArXiv]
    
    
  • H. Hatami, Kaave Hosseini, Xiang Ming, A Borsuk-Ulam lower bound for sign-rank and its applications,
    55th Annual ACM Symposium on Theory of Computing (STOC 2023). [ECCC]
    
    
  • H. Hatami and Pooya Hatami, The Implicit Graph Conjecture is False,
    63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS 2022) [arXiv]
    
    
  • H. Hatami, Kaave Hosseini, Shachar Lovett, Structure of protocols for XOR functions,
    IEEE Annual Symposium on Foundations of Computer Science (FOCS 2016) [ECCC]
    
    
  • Arnab Bhattacharyya, Eldar Fischer, H. Hatami, Pooya Hatami, Shachar Lovett, Every locally characterized affine-invariant property is testable,
    ACM Symposium on Theory of Computing. (STOC 2013) [arXiv]
    
    
• Selected Publications in other areas of Mathematics:
  
  
  • Yuval Filmus, Esty Kelman, H. Hatami, Kaave Hosseini, Sparse graph counting and Kelley-Meka bounds for binary systems,
    IEEE Annual Symposium on Foundations of Computer Science (FOCS 2024) [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, Laszlo Lovasz, Balazs Szegedy, Limits of local-global convergent graph sequences,
    Geometric and Functional Analysis, 24 (2014), no. 1, 269-296. [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, Sergey Norin, Undecidability of linear inequalities in graph homomorphism densities,
    Journal of the American Mathematical Society, 24(2) (2011), 547-565. [arXiv]
    
    

Surveys:

• H. Hatami and Pooya Hatami, Structure in Communication Complexity and Constant-Cost Complexity Classes, SIGACT news, to appear. [arXiv]
  
  
• Higher order Fourier analysis and applications, with Pooya Hatami and Shachar Lovett (Foundations and Trends in Theoretical Computer Science). You can download the prepublished draft.