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