Theory of Computing ------------------- Title : The Layer Complexity of Arthur-Merlin-like Communication Authors : Dmitry Gavinsky Volume : 17 Number : 8 Pages : 1-28 URL : https://theoryofcomputing.org/articles/v017a008 Abstract -------- In communication complexity the _Arthur-Merlin (AM)_ model is the most natural one that allows both randomness and non-determinism. 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 a subject to the discrepancy bound: for any $f$ $SLAM(f) \in \Omega(\sqrt{\log(1/disc(f))})$ In particular, the inner product function does not have an efficient SLAM-protocol. Structurally this can be summarised as $SBP \cup UAM \subset SLAM \subseteq AM\cap PP$ 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.