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