Volume 17 (2021) Article 8 pp. 1-28

The Layer Complexity of Arthur-Merlin-like Communication

by Dmitry Gavinsky

Received: May 23, 2019
Revised: December 11, 2020
Published: September 27, 2021

$\newcommand{\AM}{\mathsf{AM}} \newcommand{\SLAM}{\mathsf{SLAM}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\PP}{\mathsf{PP}} \newcommand{\MA}{\mathsf{MA}} \newcommand{\UAM}{\mathsf{UAM}} \newcommand{\SBP}{\mathsf{SBP}}$

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.

Structurally this can be summarized 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.

DOI: 10.4086/toc.2021.v017a008

© 2021 Dmitry Gavinsky
Licensed under a Creative Commons Attribution License (CC-BY)