Abstract-I en flerparti meddelande-passing modell för kommunikation, det finns k spelare. Varje spelare har en privat ingång, och de kommunicerar genom att skicka meddelanden till varandra via privata kanaler. Även om denna modell har använts i stor utsträckning i distribuerade datorer och i säker flerpartsberäkning, har lägre gränser för kommunikations komplexitet i denna modell och relaterade modeller varit något knappa. I det senaste arbetet [25], [29], [30], starka lägre gränser för formen  på (n · k) erhölls för flera funktioner i meddelandepasserande modellen; dock, en lägre gräns på den klassiska uppsättningen uppdelningsproblem förblev svårfångad. I det här dokumentet visar vi på en snäv nedre gräns för "n · k" för det uppsatta problemet med osammanhängande i den meddelandepasserande modellen. Vårt band uppnås genom att utveckla verktyg för information komplexitet för meddelande-passing modellen och bevisa en informations komplexitet lägre gräns för set osammanhängande.
I REF har det visat sig att kommunikations komplexiteten hos problemet med k-partsset-separation i meddelande-passing-modellen är bits (kn).
A Tight Bound for Set Disjointness in the Message-Passing Model
{'venue': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'journal': '2013 IEEE 54th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}