The communication complexity of the inevitable intersection problem

DOI10.4086/CJTCS.2020.003MaRDI QIDQ4988302zbMATH OpenOpenAlexFDO

Authors Dmitry Gavinsky

Publication date 14 May 2021

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

combinatoricscommunication complexityset disjointness

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Recommendations

• The randomized communication complexity of set disjointness
• From information to exact communication
• The multiparty communication complexity of set disjointness
• The Probabilistic Communication Complexity of Set Intersection
• Beyond set disjointness: the communication complexity of finding the intersection

Cited in

(7)

• Multi-party set disjointness and intersection with bounded dependence
• scientific article; zbMATH DE number 894723 (Why is no real title available?)
• scientific article; zbMATH DE number 7650118 (Why is no real title available?)
• On the P versus NP intersected with co-NP question in communication complexity
• The communication complexity of interval orders
• Beyond set disjointness: the communication complexity of finding the intersection
• The Probabilistic Communication Complexity of Set Intersection

This page was built for publication: The communication complexity of the inevitable intersection problem

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