skip to main content

Title: Lower bound for dilatations: LOWER BOUND FOR DILATATIONS
Authors:
 
Publication Date:
NSF-PAR ID:
10068899
Journal Name:
Journal of Topology
Volume:
11
Issue:
3
Page Range or eLocation-ID:
602 to 614
ISSN:
1753-8416
Publisher:
Oxford University Press (OUP)
Sponsoring Org:
National Science Foundation
More Like this
  1. Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set x ⊆ [ n ] and Bob ends up with a set y ⊆ [ n ], such that ( x , y ) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant β < 1, this requires Ω ( n ) communication even to get within statistical distance 1− β n of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that Ω (√ n ) communication is required to get within some constant statistical distance ɛ > 0 of the uniform distribution over all pairs of disjoint sets of size √ n .