Revised: December 11, 2020
Published: September 27, 2021
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.