166 citations · 310 across the 42 of their papers we have counts for
50 papers
Boolean Functions with Small Approximate Spectral Norm
Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao +1
The sum of the absolute values of the Fourier coefficients of a function is called the spectral norm of . Green and Sanders' quantitative versi…
Online Learning and Disambiguations of Partial Concept Classes
Tsun-Ming Cheung, Hamed Hatami, Pooya Hatami +1
In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central quest…
On depth-3 circuits and covering number: an explicit counter-example
Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye
We give a simple construction of Boolean matrices with zero entries that are free of all-zero submatrices and have covering number $O(\log^4(n…
The Implicit Graph Conjecture is False
Hamed Hatami, Pooya Hatami
An efficient implicit representation of an -vertex graph in a family of graphs assigns to each vertex of a binary code of length so that the ad…
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal gr…
Typical structure of hereditary properties of binary matroids
Stefan Grosser, Hamed Hatami, Peter Nelson +1
We prove an arithmetic analogue of the typical structure theorem for graph hereditary properties due to Alon, Balogh, Bollobás and Morris.