Optimality of Correlated Sampling Strategies

DOI10.4086/toc.2020.v016a012zbMath1462.68053arXiv1612.01041OpenAlexW3101751096MaRDI QIDQ5140847

Elad Haramaty, Badih Ghazi, Mohammad Bavarian, Madhu Sudan, Ronald L. Rivest, Pritish Kamath

Publication date: 17 December 2020

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.01041

zbMATH Keywords

samplingdistributionscouplingcommunication complexitycorrelated samplingMinHash

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Communication complexity, information complexity (68Q11)

Cites Work

• Parallel Repetition in Projection Games and a Concentration Bound
• Approximation algorithms for classification problems with pairwise relationships
• Probability and Computing
• Unnamed Item

This page was built for publication: Optimality of Correlated Sampling Strategies