slideshow 3

Complexity seminar

The layer complexity of Arthur-Merlin-like communication

Dmitry Gavinsky
IM CAS

 

Friday, 4. January 2019 - 13:30 to 15:00

in IM, rear building, ground floor

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 work 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 have the
following properties:
    - SLAM is (strictly) included in AM and includes all previously known sub-AM classes with non-trivial
lower bounds.
    - SLAM is qualitatively stronger than the union of those classes.
    - SLAM is a subject to the discrepancy bound: in particular, the inner product function does not have an
efficient SLAM-protocol.

Structurally this can be summarised as
SBP ∪ UAM ⊂ SLAM ⊆ AM ∩ PP.

In the second part we ask why proving a lower bound of ω(√n) on the MA-complexity of an explicit function
seems to be difficult.

Both of these results are related to the notion of layer complexity, which is, informally, the number of
“layers of non-determinism” used by a protocol. We believe that further investigation of this concept may
lead to better understanding of the communication model AM and to non-trivial lower bounds against it.