Loading...
Please wait, while we are loading the content...
Similar Documents
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Beame, Paul Pitassi, Toniann Segerlind, Nathan Wigderson, Avi |
| Description | 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 widelystudied set disjointness problem in the usual “number-onthe-forehead” (NOF) model of multiparty communication complexity. |
| File Format | |
| Language | English |
| Publisher | IEEE |
| Publisher Date | 2005-01-01 |
| Publisher Institution | IN PROCEEDINGS OF THE 20TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY |
| Access Restriction | Open |
| Subject Keyword | Direct Sum Theorem Multiparty Nof Communication Complexity Multiparty Communication Complexity Widelystudied Set Disjointness Problem Powerful Measure Direct Sum Bound Set Disjointness 2-party Randomized Communication Complexity Strong Direct Sum Property Rectangular Distribution |
| Content Type | Text |
| Resource Type | Article |