Rivest's optimality conjecture for correlated sampling
Let , let denote the uniform distribution on a finite set , and let be probabilistic strategies satisfying the correctness condition for correlated sampling. For positive integers with and , consider sets with , , and . Rivest's conjecture. For every such and every pair , there exist sets with these sizes such that
This conjecture asserts that Broder's MinHash correlated-sampling strategy is optimal except in the case of intersection size one covered by Rivest's protocol. The paper's main result proves the asserted lower bound for constant-fraction intersections, while the fully general statement remains open.
References
- Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest and Madhu Sudan, “Optimality of Correlated Sampling Strategies”, arXiv:1612.01041 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.