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.