201 citations · 235 across the 24 of their papers we have counts for
Showing 2021Show all
2 papers · 1 filter
math.CO2021
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…
cs.CC2021★ 1 cited
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…