All reports by Author TsunMing Cheung:

__
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-041
| 23rd March 2022
__

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

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

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