Computer Science/Discrete Mathematics Seminar I

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.)