Sammanfattning -Kommunikations komplexitet av en tvåvariabel funktion f ( x, y ) är antalet information bits två kommunikatörer behöver utbyta för att beräkna f när, initialt, var och en vet bara en av variablerna. Det finns flera kommunikation-komplexitet åtgärder som motsvarar om 1) det värsta fallet eller genomsnittliga antalet bitar beaktas, 2) beräkningsfel är tillåtna eller inte, och 3) randomisering är tillåtet eller inte. Täta gränser tillhandahålls för det typiska beteendet hos alla bundna-terror kommunikation-komplexitet åtgärder av Booleska funktioner. Låt 3 vara denna funktionsf: { 0 ;~~, n - l ) X { 0 ;~~, n - l } - t { O, l) som innehåller de (dvs. I { x, v ) : f( x, y) = 1} 1 =s). Det visas att för varje n I s I i 2 / 2 de kommunikation-komplexitet åtgärder faller i två klasser: logpi cluss -den felfria värsta fall randomiserade komplexitet och, ännu viktigare, den felfria värsta fall deterministiska komplexiteten hos de flesta funktioner i 3 är mellan log n -4 och log n + 1 bits (detta håller även f o r s = n ) ; /og(s/n) cluss-c-terror värsta fall randomiserade komplexitet och c-terror genomsnittliga randomiserade komplexitet av de flesta funktioner i e är mellan (1 -2c) (s/ n ) -2 log log log log ( s / n ) och (1 -2c) (log(s/s/n) + 5.3 loglog n) bitar. Viktigare är att den felfria genomsnittliga deterministiska komplexiteten hos alla funktioner i är mindre än log(s/n)+8.3loglogn bitar. För de flesta av dessa funktioner är det också t log(s/n) -2logloglog(s/n) bits. Skillnaden mellan komplexiteten i log n klassen och l o g ( s / n ) klass varierar från en konstant (för s = n2/2) till exponentiell (för s --n log n ). I synnerhet, eftersom de flesta funktioner har ungefär n2/2 sådana, alla deras komplexitet åtgärder är runt log n bitar. Ommunication komplexitet först infördes C av Abelson [l] och Yao [2]. Det handlar om olika aspekter av följande problem: n är ett positivt heltal, f är en binär funktion definieras på (0,. -, n -1) X (0;. -, n -l }, och c 2 0. Två kommunikatörer, P, som har ett slumpmässigt heltal X E (0;. ., n -1} och P, med ett slumpmässigt heltal Y E (0;.., n -l}, använda ett förutbestämt protokoll för att beräkna f( X, Y ) med sannolikhet för fel I c. Hur många bitar måste de byta i genomsnitt? I värsta fall? De två följande avsnitten gör dessa begrepp mer exakta: I avsnitt I1 definierar vi formellt den deterministiska modellen; i avsnitt I11 beskriver vi randomiserade protokoll och jämför dem med deterministiska. I avsnitt IV kartlägger vi tidigare arbete och beskriver de resultat som erhållits i detta dokument. Dessa resultat visas i Avsnitt V. Kommunikation utförs över en binär kanal som kan bära endast en bit i taget. Därför sänder varje kommunikator i sin tur en (möjligt tom) sekvens av bitar som vi kallar en sträng eller ett meddelande. Eftersom tomma meddelanden är tillåtna förlorar vi ingen allmänhet genom att anta att Px sänder det första meddelandet. Kommunikationen sker enligt ett förutbestämt protokoll som vid varje tidpunkt anger vilket meddelande som överförs och vid slutet av kommunikationen beslutar om det beräknade värdet som kommunikatörerna (P och P) antar är det korrekta värdet av funktionen. Protokollet är deterministiskt om, när P, och P, har samma par slumpmässiga heltal, de överför samma sekvens av meddelanden och besluta om samma beräknade värde. Med denna kommunikationsmodell i åtanke definierar vi formellt deterministiska protokoll. Definitionen liknar den för [3] och [4]. Det skiljer sig från [3] genom att 1) det betraktar protokollet som en kodbok (ett tillvägagångssätt som underlättar informations-teoretisk behandling), och 2) det beräknade värdet av funktionen inte behöver överföras explicit. En inmatning är en beställd par O,~~~, n -l }~~~~, n -l } kan därför definieras som en kartläggning som associerar med varje ingång.
Den genomsnittliga och randomiserade komplexiteten hos Booleska funktioner studeras i REF.
Average and Randomized Communication Complexity
{'venue': 'IEEE Trans. Inf. Theory', 'journal': 'IEEE Trans. Inf. Theory', 'mag_field_of_study': ['Computer Science']}