Communication complexity
The notion of communication complexity was introduced by Yao in 1979,who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations.
Wikipage redirect
primaryTopic
Communication complexity
The notion of communication complexity was introduced by Yao in 1979,who investigated the following problem involving two separated parties (Alice and Bob). Alice receives an n-bit string x and Bob another n-bit string y, and the goal is for one of them (say Bob) to compute a certain function f(x,y) with the least amount of communication between them. Note that here we are not concerned about the number of computational steps, or the size of the computer memory used. Communication complexity tries to quantify the amount of communication required for such distributed computations.
has abstract
A noção de complexidade de com ...... livro de Kushilevitz e Nisan.
@pt
Die Kommunikationskomplexität ...... ourcenbedarf von Berechnungen.
@de
La complexité de la communicat ...... t le design des circuits VLSI.
@fr
The notion of communication co ...... book by Kushilevitz and Nisan.
@en
通信複雑性（つうしんふくざつせい、Communication ...... る Kushilevitz と Nisan の著書に詳しい。
@ja
Link from a Wikipage to an external page
Wikipage page ID
Wikipage revision ID
742,524,419
subject
comment
A noção de complexidade de com ...... ssas computações distribuídas.
@pt
Die Kommunikationskomplexität ...... ourcenbedarf von Berechnungen.
@de
La complexité de la communicat ...... nimiser le nombre de messages.
@fr
The notion of communication co ...... such distributed computations.
@en
通信複雑性（つうしんふくざつせい、Communication ...... る Kushilevitz と Nisan の著書に詳しい。
@ja
label
Communication complexity
@en
Complexidade de comunicação
@pt
Complexité de la communication
@fr
Kommunikationskomplexität
@de
通信複雑性
@ja