The Communication Complexity of Number-In-Hand Set Disjointness with No Promise.

Mark Braverman Rotem Oshman

Published in: Electron. Colloquium Comput. Complex. (2015)

Keyphrases

small number
computational complexity
fixed number
maximum number
finite number
initial set
polynomial time complexity
small fraction
worst case
memory requirements
equally spaced
probability distribution
space complexity
approximation error
np complete
average distance