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.