Communication complexity
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them.
academic discipline
known for
Wikipage redirect
Active networkingAlon OrlitskyAndrew YaoAshok K. ChandraComputational complexity theoryConcentration inequalityDistributed computingExponential time hypothesisExtension of a polyhedronGap-Hamming problemGreenberger–Horne–Zeilinger stateHarry BuhrmanJaikumar RadhakrishnanList of pioneers in computer scienceLog-rank conjectureMatrix normMultiparty communication complexityOded Regev (computer scientist)Picking sequencePredecessor problemProof complexityProof of secure erasureQuantum communication complexityQuantum information scienceRandomized algorithmRank (linear algebra)Richard CleveRonald de WolfStreaming algorithmTheoretical computer scienceTuring Award
Link from a Wikipage to another Wikipage
known for
primaryTopic
Communication complexity
In theoretical computer science, communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. The study of communication complexity was first introduced by Andrew Yao in 1979, while studying the problem of computation distributed among several machines.The problem is usually stated as follows: two parties (traditionally called Alice and Bob) each receive a (potentially different) -bit string and . The goal is for Alice to compute the value of a certain function, , that depends on both and , with the least amount of communication between them.
has abstract
A noção de complexidade de com ...... livro de Kushilevitz e Nisan.
@pt
Die Kommunikationskomplexität ...... ourcenbedarf von Berechnungen.
@de
In theoretical computer scienc ...... e field, see the textbook by .
@en
La complexité de la communicat ...... t le design des circuits VLSI.
@fr
В теоретической информатике ко ...... зательств и в других областях.
@ru
通信複雑性（つうしんふくざつせい、Communication ...... る Kushilevitz と Nisan の著書に詳しい。
@ja
Link from a Wikipage to an external page
Wikipage page ID
page length (characters) of wiki page
Wikipage revision ID
1,024,365,130
Link from a Wikipage to another Wikipage
wikiPageUsesTemplate
subject
comment
A noção de complexidade de com ...... ssas computações distribuídas.
@pt
Die Kommunikationskomplexität ...... ourcenbedarf von Berechnungen.
@de
In theoretical computer scienc ...... of communication between them.
@en
La complexité de la communicat ...... nimiser le nombre de messages.
@fr
В теоретической информатике ко ...... f существует способ вычислить
@ru
通信複雑性（つうしんふくざつせい、Communication ...... る Kushilevitz と Nisan の著書に詳しい。
@ja
label
Communication complexity
@en
Complexidade de comunicação
@pt
Complexité de la communication
@fr
Kommunikationskomplexität
@de
Коммуникационная сложность
@ru
通信複雑性
@ja