A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness
Paul W. Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson · 2005
We prove that corruption, one of the most powerful measures used to analyze 2-party randomized communication complexity, satisfies a strong direct sum property under rectangular distributions. This direct sum bound holds even when the error is allowed to be exponentially close to 1. We use this to analyze the complexity of the widely-studied set disjointness problem in the usual "number-on-the-forehead" (NOF) model of multiparty communication complexity.