Multi-party set disjointness and intersection with bounded dependence

DOI10.1145/3662158.3662795MaRDI QIDQ6971938zbMATH OpenFDO

Authors Mark Braverman, Rotem Oshman

Publication date 13 June 2025

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

zbMATH Keywords

communication protocolscorrelationset disjointnessset intersection

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites work

• A tight bound for set disjointness in the message-passing model
• Beyond set disjointness: the communication complexity of finding the intersection
• Communication Complexity
• Communication complexity theory: thirty-five years of set disjointness
• Communication complexity with small advantage
• Correlation in Hard Distributions in Communication Complexity
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Elements of Information Theory
• From information to exact communication
• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• Information Theoretical Analysis of Multivariate Correlation
• Interactive compression for multi-party protocol
• Linear dependence structure of the entropy space
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• On information complexity in the broadcast model
• On the communication complexity of sparse set disjointness and exists-equal problems
• The communication complexity of multiparty set disjointness under product distributions
• The communication complexity of set intersection and multiple equality testing
• The communication complexity of set intersection under product distributions
• The communication complexity of the inevitable intersection problem

This page was built for publication: Multi-party set disjointness and intersection with bounded dependence

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