Communication Complexity with Small Advantage
- PDF / 583,414 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 208 Views
computational complexity
COMMUNICATION COMPLEXITY WITH SMALL ADVANTAGE Thomas Watson
Abstract. We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least greater than one over the codomain size of the function. Previously, Braverman and Moitra (in: Proceedings of the 45th symposium on theory of computing (STOC), ACM, pp 161–170, 2013) showed that the set-intersection function requires Θ(n) communication to achieve advantage . Building on this, we prove the same bound for several variants of set-intersection: (1) the classic “tribes” function obtained by composing with And (provided 1/ is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate. Keywords. Communication complexity, Small advantage Subject classification. 68Q17
1. Introduction In randomized communication complexity, protocols are commonly required to succeed with probability at least some constant less than 1, such as 3/4. Achieving success probability one over the codomain size of the function is trivial by outputting a uniformly random guess. There is a spectrum of complexities between these extremes, where we require a protocol to achieve success probability greater than one over the codomain size, i.e., advantage . We study the fine-grained question “How does the communication complexity of achieving advantage depend on ?” 0123456789().: V,-vol
2
Page 2 of 37
T. Watson
cc
Formally, for a two-party function F , let Rp (F ) denote the minimum worst-case communication cost of any randomized protocol (with both public and private coins) that is p-correct in the sense that for each input (X, Y ) in the domain of F , it outputs F (X, Y ) with probability at least p. First, let us consider functions with codomain size 2. One observation is that running an advantage- protocol O(1/2 ) times independently and taking the majority outcome yields an advantage1/4 protocol (we call this “majority-amplification”): R1/2+ (F ) ≥ Ω(2 R3/4 (F )). However, this does not tell the whole story; achieving advantage may be harder than this bound suggests, depending on the function. For example, consider the well-studied functions Inner-Prod (inner product mod 2), Set-Inter (set-intersection, where 1-inputs are intersecting), and Gap-Hamming (determin√ √ ing whether the Hamming distance is ≥ n/2 + n or ≤ n/2 − n). Each of these three functions F satisfies R3/4 (F ) = Θ(n), and yet −o(n) r R 1/2+ (Inner-Prod) = Θ(n) provided ≥ 2
(Chor & Goldreich 1988);
r R 1/2+ (Set-Inter) = Θ(n) provided n ≥ 1
(Braverman & Moitra 2013; G¨oo¨s & Watson 2016);
2 2 r R 1/2+ (Gap-Hamming) = Θ( n) provided n ≥ 1
(Chakrabarti & Regev 2012; Sherstov 2012; Vidick 2012). (We provide a proof of the Gap-Hamming upper bound in A since it does not appear in the
Data Loading...
