DocumentCode :
655242
Title :
Direct Products in Communication Complexity
Author :
Braverman, Mark ; Rao, Akhila ; Weinstein, Omri ; Yehudayoff, Amir
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., Princeton, NJ, USA
fYear :
2013
fDate :
26-29 Oct. 2013
Firstpage :
746
Lastpage :
755
Abstract :
We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f, C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μn be the product distribution on n inputs and fn denote the function that computes n copies of f on these inputs. We prove that if T log3/2 T ≪ (C - 1)√n and suc(μ, f, C) <; 2/3, then suc(μn, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log2 T ≪ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)).
Keywords :
Boolean functions; communication complexity; probability; 2-party communication protocol; Boolean function; communication complexity; product distribution; Complexity theory; Computational modeling; Computer science; Educational institutions; Mutual information; Protocols; Upper bound; Communication Complexity; Direct Products; Information Complexity;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on
Conference_Location :
Berkeley, CA
ISSN :
0272-5428
Type :
conf
DOI :
10.1109/FOCS.2013.85
Filename :
6686211
Link To Document :
بازگشت