Vi studerar beräkningskraften hos den överbelastade klicken, en modell för distribuerad beräkning där n-spelare kommunicerar med varandra över ett komplett nätverk för att beräkna någon funktion av sina ingångar. Antalet bitar som kan skickas på valfri kant i en runda begränsas av en parameter b. Vi överväger två versioner av modellen: i den första, spelarna kommunicerar med unicast, så att de kan skicka ett annat meddelande på var och en av sina länkar i en omgång; i den andra, spelarna kommunicerar via sändning, skicka ett meddelande till alla sina grannar. Det är känt att den unicastade versionen av modellen är ganska kraftfull; hittills är inga lägre gränser för denna modell kända. I detta papper ger vi en partiell förklaring genom att visa att den engjutna kliquen kan simulera kraftfulla klasser av avgränsade djupkretsar, vilket innebär att även något super-konstant nedre gränser för den överbelastade kliquen skulle ge nya lägre gränser i kretsen komplexitet. Dessutom, under en allmänt trod gissning om matris multiplikation, triangeln detektion problem, studeras i [8], kan lösas i O(n ) tid för alla > 0. Sändningsversionen av den överbelastade klicken är den välkända flerpartsmodellen med delad svart tavla av kommunikationskomplexitet (med indata i siffror). Denna version är mer amenable till lägre gränser, och i detta papper visar vi att subgraph detektion problem studeras i [8] kräver polynomialt många rundor för flera klasser av subgrafer. Vi ger också övre gränser för subgraf detektion problem, och relaterar hårdheten av triangeln detektion i sändningen överbelastade klick till kommunikations komplexiteten av set uppdelning i 3-parts tal-on-forehead-modellen.
Dessutom, för sändningen överbelastade klick, en version av modellen där varje nod skickar samma meddelande till varandra nod varje runda, lägre gränser har bevisats med hjälp av kommunikations komplexitet argument REF.
On the power of the congested clique model
{'venue': "PODC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}