All reports by Author Hamed Hatami:

__
TR23-050
| 18th April 2023
__

Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen#### Communication complexity of half-plane membership

__
TR22-165
| 22nd November 2022
__

TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley#### Separation of the factorization norm and randomized communication complexity

__
TR22-130
| 15th September 2022
__

Hamed Hatami, Kaave Hosseini, Xiang Meng#### A Borsuk-Ulam lower bound for sign-rank and its application

__
TR22-079
| 25th May 2022
__

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao#### Lower Bound Methods for Sign-rank and their Limitations

__
TR22-041
| 23rd March 2022
__

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein#### Boolean functions with small approximate spectral norm

__
TR21-123
| 25th August 2021
__

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani#### On public-coin zero-error randomized communication complexity

Revisions: 2

__
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

Revisions: 1

__
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

Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen

We study the randomized communication complexity of the following problem. Alice receives the integer coordinates of a point in the plane, and Bob receives the integer parameters of a half-plane, and their goal is to determine whether Alice's point belongs to Bob's half-plane.

This communication task corresponds to determining ... more >>>

TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley

In an influential paper, Linial and Shraibman (STOC '07) introduced the factorization norm as a powerful tool for proving lower bounds against randomized and quantum communication complexities. They showed that the logarithm of the approximate $\gamma_2$-factorization norm is a lower bound for these parameters and asked whether a stronger ... more >>>

Hamed Hatami, Kaave Hosseini, Xiang Meng

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

The sign-rank of a matrix $A$ with $\pm 1$ entries is the smallest rank of a real matrix with the same sign pattern as $A$. To the best of our knowledge, there are only three known methods for proving lower bounds on the sign-rank of explicit matrices: (i) Sign-rank is ... more >>>

TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>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 >>>