The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties. 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.

PropertyValue
dbpprop:abstract
  • The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties. 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. Of course they can always succeed by having Alice send her whole n-bit string to Bob, who then computes the function, but the idea here is to find clever ways of calculating f with less than n bits of communication. This abstract problem is relevant in many contexts: in VLSI circuit design, for example, one wants to minimize energy used by decreasing the amount of electric signals required between the different components during a distributed computation. The problem is also relevant in the study of data structures, and in the optimization of computer networks. For a survey of the field, see the book by Kushilevitz and Nisan.
  • 通信複雑性（つうしんふくざつせい、Communication Complexity、CC）は、1979年にアンドリュー・チーチー・ヤオによって導入された用語。ヤオは2つの個体間の通信問題を研究していた。アリスは n ビットの文字列 x を受信し、ボブも別の n ビットの文字列 y を受信する。目標は両者のいずれかが最小限の通信によって関数 f(x,y) を計算することである。ここでは、計算のステップ数を問題にしているのでも、計算に必要なメモリ量を問題にしているのでもない。通信複雑性とは、このような分散計算で必要となる通信の量を測るものである。 もちろん、上記の例でアリスが n ビットの文字列全体をボブに送ってしまえば、ボブがその関数を計算でき、問題は解決する。しかし、ここで考えているのは、n ビットより少ない通信量で関数を計算する賢い手法の探索である。 この抽象的な問題は様々な場面で応用できる。VLSIの回路設計では、消費電力を低減させるために、ある部分から別の部分に流れる信号の量を最小化したい場合がある。他にもデータ構造の研究やコンピュータネットワークの最適化にも関連する。応用に関しては、参考文献にある Kushilevitz と Nisan の著書に詳しい。
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties. 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.
rdfs:label
  • Communication complexity
  • 通信複雑性
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of