NP and MA Do Not Contain coNP in Multiparty Communication Complexity

COMPUTER SCIENCE/DISCRETE MATH I
Topic:NP and MA Do Not Contain coNP in Multiparty Communication Complexity
Speaker:Dmitry Gavinsky
Affiliation:NEC Laboratories America, Inc.
Date:Monday, March 9
Time/Room:11:15am - 12:15pm/S-101

We prove that NP is different from coNP and coNP is not a subset of MA in the number-on-forehead model of multiparty communication complexity for up to k=(1 - e)log(n) players, where e>0 is any constant. Prior to our work, the problem was open even for k = 3 players. (This is joint work with A.Sherstov.)