Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Morgan Shirley:

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-152 | 10th November 2022
Toniann Pitassi, Morgan Shirley, Adi Shraibman

The Strength of Equality Oracles in Communication

It is well-known that randomized communication protocols are more powerful than deterministic protocols. In particular the Equality function requires $\Omega(n)$ deterministic communication complexity but has efficient randomized protocols. Previous work of Chattopadhyay, Lovett and Vinyals shows that randomized communication is strictly stronger than what can be solved by deterministic protocols ... more >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

ISSN 1433-8092 | Imprint