A probabilistic distributed algorithm for set intersection and its analysis

DOI10.1016/0304-3975(87)90010-7zbMath0612.68039OpenAlexW1997362133MaRDI QIDQ1088406

Udi Manber, Thomas G. Kurtz

Publication date: 1987

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://digital.library.wisc.edu/1793/58568

zbMATH Keywords

Markov chainsprobabilistic algorithmdistributed computingamount of communicationset disjointness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Combinatorial techniques for universal hashing, Hash challenges: stretching the limits of compare-by-hash in distributed data deduplication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A probabilistic lower bound for checking disjointness of sets
• Strong approximation theorems for density dependent Markov chains
• Universal classes of hash functions
• The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
• Applications of Ramsey's theorem to decision tree complexity
• On the Optimality of Some Set Algorithms