Theory of Computing
-------------------
Title : The Layer Complexity of Arthur-Merlin-like Communication
Authors : Dmitry Gavinsky
Volume : 17
Number : 8
Pages : 1-28
URL : http://www.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.