2026-07-21T14:18:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5076 2024-03-06T10:35:45Z ddc:004 open_access

Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness Rao, Anup Yehudayoff, Amir communication complexity set disjointness number on forehead lower bounds We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anup Rao and Amir Yehudayoff 2015 Is Part Of LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2015.88 urn:nbn:de:0030-drops-50769 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.88 eng https://creativecommons.org/licenses/by/3.0/legalcode