Beyond set disjointness: the communication complexity of finding the intersection

DOI10.1145/2611462.2611501MaRDI QIDQ2943615zbMATH OpenOpenAlexFDO

Authors Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev

Publication date 3 September 2015

Published in Proceedings of the 2014 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2611462.2611501

zbMATH Keywords

big datacommunication complexitycommunication protocolsdatabasesdistributed algorithms

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Database theory (68P15) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Certifying equality with limited interaction
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of the inevitable intersection problem
• The communication complexity of set intersection and multiple equality testing
• Deterministic communication complexity of set intersection

Cited in

(25)

• A new optimal distributed algorithm for the set intersection problem
• Still another rank determination of set intersection matrices with an application in communication complexity
• Deterministic communication complexity of set intersection
• Lower bounds for set intersection queries
• Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond
• Communication complexity with small advantage
• Communication complexity of set-disjointness for all probabilities
• scientific article; zbMATH DE number 6696541 (Why is no real title available?)
• Certifying equality with limited interaction
• The Simultaneous Communication of Disjointness with Applications to Data Streams
• Set reconciliation with nearly optimal communication complexity
• The Probabilistic Communication Complexity of Set Intersection
• scientific article; zbMATH DE number 894723 (Why is no real title available?)
• The communication complexity of the inevitable intersection problem
• Distributed Testing of Distance-k Colorings
• scientific article; zbMATH DE number 7250149 (Why is no real title available?)
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of set intersection and multiple equality testing
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• The communication complexity of functions with large outputs
• Communication cost of joins over federated data
• The communication complexity of distributed maximization
• Multi-party set disjointness and intersection with bounded dependence
• On distributed differential privacy and counting distinct elements

This page was built for publication: Beyond set disjointness: the communication complexity of finding the intersection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943615)