caa a22 4500 467909644 CHVBK 20180406152845.0 cr unu---uuuuu 170328e20061201xx s 000 0 eng 10.1007/s00037-007-0220-2 doi (NATIONALLICENCE)springer-10.1007/s00037-007-0220-2 A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness [Elektronische Daten] [Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson] Abstract.: We prove that two-party randomized communication complexity satisfies a strong direct product property, so long as the communication lower bound is proved by a "corruption” or "one-sided discrepancy” method over a rectangular distribution. We use this to prove new n Ω(1) lower bounds for 3-player number-on-the-forehead protocols in which the first player speaks once and then the other two players proceed arbitrarily. Using other techniques, we also establish an Ω(n 1/(k−1)/(k − 1)) lower bound for k-player randomized number-on-the-forehead protocols for the disjointness function in which all messages are broadcast simultaneously. A simple corollary of this is that general randomized number-on-the-forehead protocols require Ω(log n/(k − 1)) bits of communication to compute the disjointness function. Birkhäuser Verlag, Basel, 2007 Communication complexity nationallicence direct product nationallicence direct sum nationallicence multiparty protocols nationallicence lower bounds nationallicence 68Q10 nationallicence 68Q15 nationallicence 68Q17 nationallicence 06D15 nationallicence 06E30 nationallicence Beame Paul Computer Science & Engineering, University of Washington, 98195-2350, Seattle, WA, USA aut Pitassi Toniann Department of Computer Science, University of Toronto, M5S 1A4, Toronto, ON, Canada aut Segerlind Nathan Department of Computer Science, Portland State University, 97207-0751, Portland, OR, USA aut Wigderson Avi School of Mathematics, Institute for Advanced Study, 05840, Princeton, NJ, USA aut computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 391-432 1016-3328 15:4<391 2006 15 37 https://doi.org/10.1007/s00037-007-0220-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-007-0220-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Beame Paul Computer Science & Engineering, University of Washington, 98195-2350, Seattle, WA, USA aut NATIONALLICENCE 700 1- Pitassi Toniann Department of Computer Science, University of Toronto, M5S 1A4, Toronto, ON, Canada aut NATIONALLICENCE 700 1- Segerlind Nathan Department of Computer Science, Portland State University, 97207-0751, Portland, OR, USA aut NATIONALLICENCE 700 1- Wigderson Avi School of Mathematics, Institute for Advanced Study, 05840, Princeton, NJ, USA aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 391-432 1016-3328 15:4<391 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer