Paper Info
Title
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems
Abstract
In this paper we study the two player randomized communication complexity of the sparse set disjoint ness and the exists-equal problems and give matching lower and upper bounds (up to constant factors) for any number of rounds for both of these problems. In the sparse set disjoint ness problem, each player receives a k-subset of [m] and the goal is to determine whether the sets intersect. For this problem, we give a protocol that communicates a total of 脮(k log(r)k) bits over r rounds and errs with very small probability. Here we can take r=log*k to obtain a 脮(k) total communication log*k-round protocol with exponentially small error probability, improving on the 脮(k)-bits 脮(log k)-round constant error probability protocol of H氓stad and Wigderson from 1997. In the exists-equal problem, the players receive vectors x, y in[t]n and the goal is to determine whether there exists a coordinate i such that x_i=y_i. Namely, the exists-equal problem is the OR of n equality problems. Observe that exists-equal is an instance of sparse set disjoint ness with k=n, hence the protocol above applies here as well, giving an 脮(n log(r)n) upper bound. Our main technical contribution in this paper is a matching lower bound: we show that when t=Ω(n), any r-round randomized protocol for the exists-equal problem with error probability at most 1/3 should have a message of size Ω(n log(r)n). Our lower bound holds even for super-constant r ≤ log*n, showing that any 脮(n) bits exists-equal protocol should have log*n - O(1) rounds. Note that the protocol we give errs only with less than polynomially small probability and provides guarantees on the total communication for the harder set disjoint ness problem, whereas our lower bound holds even for constant error probability protocols and for the easier exists-equal problem with guarantees on the max-communication. Hence our upper and lower bounds match in a strong sense. Our lower bound on the constant round protocols for exists-equal shows that solving the OR of n instances of the equality problems requires strictly more than n times the cost of a single instance. To our knowledge this is the first example of such a super-linear increase in complexity.
Year
DOI
Venue
2013
10.1109/FOCS.2013.78
foundations of computer science
Keywords
DocType
Volume
disjoint ness problem,communication complexity,exists-equal problems,log k,n log,easier exists-equal problem,sparse set disjointness,exists-equal shows,bits exists-equal protocol,k log,total communication log,exists-equal problem,disjoint ness,set theory,lower bound,computational complexity,upper bound,game theory,error probability
Conference
abs/1304.1217
ISSN
Citations 
PageRank 
0272-5428
12
0.59
References 
Authors
32
2
Name
Order
Citations
PageRank
Mert Saglam1221.35
Gábor Tardos21261140.58