All reports by Author Morgan Shirley:

__
TR23-138
| 12th September 2023
__

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman#### An improved protocol for ExactlyN with more than 3 players

__
TR22-165
| 22nd November 2022
__

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

__
TR22-152
| 10th November 2022
__

Toniann Pitassi, Morgan Shirley, Adi Shraibman#### The Strength of Equality Oracles in Communication

__
TR19-043
| 12th March 2019
__

Toniann Pitassi, Morgan Shirley, Thomas Watson#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman

The ExactlyN problem in the number-on-forehead (NOF) communication setting asks $k$ players, each of whom can see every input but their own, if the $k$ input numbers add up to $N$. Introduced by Chandra, Furst and Lipton in 1983, ExactlyN is important for its role in understanding the strength of ... 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 >>>

Toniann Pitassi, Morgan Shirley, Adi Shraibman

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

Toniann Pitassi, Morgan Shirley, Thomas Watson

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