Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR22-165 | 22nd November 2022
TsunMing Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley

Separation of the factorization norm and randomized communication complexity

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

TR22-041 | 23rd March 2022
TsunMing Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

Boolean functions with small approximate spectral norm

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

ISSN 1433-8092 | Imprint