Revised: December 11, 2020

Published: September 27, 2021

**Keywords:**communication complexity, complexity classes

**ACM Classification:**F.1.3

**AMS Classification:**68Q15

**Abstract:**
[Plain Text Version]

In communication complexity the *Arthur-Merlin* $(\AM)$ model is the most natural one that allows both randomness and nondeterminism.
Presently we do not have any super-logarithmic lower bound for the $\AM$-complexity of an explicit function.
Obtaining such a bound is a fundamental challenge to our understanding of communication phenomena.

In this article
we explore the gap between the known techniques and the complexity class $\AM$.
In the first part we define a new natural class,
*Small-advantage Layered Arthur-Merlin* $(\SLAM)$,
that has the following properties:

- $\SLAM$ is (strictly) included in $\AM$ and includes all previously known subclasses of $\AM$ with non-trivial lower bounds: $$\NP, \MA, \SBP, \UAM \subseteq \SLAM \subset \AM$$ Note that $\NP\subset\MA\subset\SBP$, while $\SBP$ and $\UAM$ are known to be incomparable.
- $\SLAM$ is qualitatively stronger than the union of those classes: $$f\in\SLAM\setminus(\SBP\cup\UAM)$$ holds for an (explicit) partial function $f$.
- $\SLAM$ is subject to the discrepancy bound: for any $f$ $$\SLAM(f) \in \Omega\left(\sqrt{\log{\frac1{disc(f)}}}\right)\,.$$ In particular, the inner product function does not have an efficient $\SLAM$-protocol.

In the second part we ask why proving a lower bound of $\omega(\sqrt n)$ on the $\MA$-complexity of an explicit function seems to be difficult. We show that such a bound either must explore certain “uniformity” of $\MA$ (which would require a rather unusual argument), or would imply a non-trivial lower bound on the $\AM$-complexity of the same function.

Both of these results are related to the notion of *layer complexity*, which is, informally, the number of “layers of nondeterminism” used by a protocol.