All reports by Author Hamed Hatami:

__
TR21-066
| 5th May 2021
__

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami#### Dimension-free Bounds and Structural Results in Communication Complexity

__
TR19-067
| 6th May 2019
__

Hamed Hatami, Kaave Hosseini, Shachar Lovett#### Sign rank vs Discrepancy

__
TR19-029
| 20th February 2019
__

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman#### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

__
TR16-190
| 21st November 2016
__

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li#### Trading information complexity for error

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>

Hamed Hatami, Kaave Hosseini, Shachar Lovett

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.

In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank ...
more >>>

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.

For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ...
more >>>