All reports by Author Tsun-Ming Cheung:

__
TR23-108
| 21st July 2023
__

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui#### Classical simulation of one-query quantum distinguishers

__
TR23-050
| 18th April 2023
__

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

Revisions: 1

__
TR22-165
| 22nd November 2022
__

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

__
TR22-041
| 23rd March 2022
__

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

Andrej Bogdanov, Tsun-Ming Cheung, Krishnamoorthy Dinesh, John C.S. Lui

We study the relative advantage of classical and quantum distinguishers of bounded query complexity over $n$-bit strings, focusing on the case of a single quantum query. A construction of Aaronson and Ambainis (STOC 2015) yields a pair of distributions that is $\epsilon$-distinguishable by a one-query quantum algorithm, but $O(\epsilon k/\sqrt{n})$-indistinguishable ... more >>>

Manasseh Ahmed, Tsun-Ming 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 >>>

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

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