Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rosie Zhao:

TR22-079 | 25th May 2022
Hamed Hatami, Pooya Hatami, William Pires, Ran Tao, Rosie Zhao

Lower Bound Methods for Sign-rank and their Limitations

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

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