A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness
P Beame, T Pitassi, N Segerlind… - 20th Annual IEEE …, 2005 - ieeexplore.ieee.org
P Beame, T Pitassi, N Segerlind, A Wigderson
20th Annual IEEE Conference on Computational Complexity (CCC'05), 2005•ieeexplore.ieee.orgWe 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.
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.
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.
ieeexplore.ieee.org