Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GAMMA_2 NORM:
Reports tagged with gamma_2 norm:
TR25-088 | 1st July 2025
Igor Balla, Lianna Hambardzumyan, Istvan Tomon

Factorization norms and an inverse theorem for MaxCut

We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_2$-norm and discuss applications in communication complexity, operator theory, spectral ... more >>>


TR25-100 | 15th July 2025
Mika Göös, Nathaniel Harms, Artur Riazanov

Equality is Far Weaker Than Constant-Cost Communication

We exhibit an $n$-bit communication problem with a constant-cost randomized protocol but which requires $n^{\Omega(1)}$ deterministic (or even non-deterministic) queries to an Equality oracle. Therefore, even constant-cost randomized protocols cannot be efficiently "derandomized" using Equality oracles. This improves on several recent results and answers a question from the survey of ... more >>>




ISSN 1433-8092 | Imprint