pdf icon
Volume 17 (2021) Article 8 pp. 1-28
The Layer Complexity of Arthur-Merlin-like Communication
Received: May 23, 2019
Revised: December 11, 2020
Published: September 27, 2021
Download article from ToC site:
[PDF (301K)] [PS (1586K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: communication complexity, complexity classes
Categories: complexity theory, complexity classes, communication complexity, Arthur-Merlin
ACM Classification: F.1.3
AMS Classification: 68Q15

Abstract: [Plain Text Version]

$ \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.