Theory of Computing
-------------------
Title : A Separation of NP and coNP in Multiparty Communication Complexity
Authors : Dmitry Gavinsky and Alexander A. Sherstov
Volume : 6
Number : 10
Pages : 227-245
URL : https://theoryofcomputing.org/articles/v006a010
Abstract
--------
We prove that coNP \not\subseteq MA in the number-on-forehead model
of multiparty communication complexity for up to k=(1-\epsilon)\log n
players, where \epsilon > 0 is any constant. Specifically, we construct
an explicit function F: ({0,1}^n)^k --> {0,1} with co-nondeterministic
complexity O(\log n) and Merlin-Arthur complexity n^{\Omega(1)}. The
problem was open for k \geq 3. As a corollary, we obtain an explicit
separation of NP and coNP for up to k=(1-\epsilon)\log n players,
complementing an independent result by Beame et al. (2010) who separate
these classes nonconstructively for up to k = 2^{(1-\epsilon)n} players.