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.
- Comment
- enIn 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
- enIn 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. While Alice and Bob can always succeed by having Bob send his whole -bit string to Alice (who then computes the function ), the idea here is to find clever ways of calculating with fewer than bits of communication. Note that, unlike in computational complexity theory, communication complexity is not concerned with the amount of computation performed by Alice or Bob, or the size of the memory used, as we generally assume nothing about the computational power of either Alice or Bob. This abstract problem with two parties (called two-party communication complexity), and its general form with more than two parties, is relevant in many contexts. In VLSI circuit design, for example, one seeks to minimize energy used by decreasing the amount of electric signals passed 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 surveys of the field, see the textbooks by and .
- Is primary topic of
- Communication complexity
- Label
- enCommunication complexity
- Link from a Wikipage to an external page
- arxiv.org/abs/quant-ph/0101005
- www.sciencedirect.com/science/article/pii/S030439759600062X/pdf%3Fmd5=673842d5f5b8a83d07e2c183ffa357a1&pid=1-s2.0-S030439759600062X-main.pdf&_valck=1
- u.cs.biu.ac.il/~zarosih/70/files/private_vs__common_random_bits_in_commun_493418.pdf
- Link from a Wikipage to another Wikipage
- Alice and Bob
- Andrew Yao
- Bit
- Category:Communication
- Category:Computational complexity theory
- Category:Quantum complexity theory
- Communication
- Computational complexity
- Computational complexity theory
- Computer memory
- Decision tree complexity
- Distributed computation
- Dot product
- Finite field
- Function (mathematics)
- Gap-Hamming problem
- Hoeffding's inequality
- Matrix (mathematics)
- Multiparty communication complexity
- Nonnegative rank (linear algebra)
- Optical fiber
- Photons
- Protocol (computing)
- Quantum entanglement
- Qubit
- Rank (linear algebra)
- Ran Raz
- Space–time tradeoff
- Streaming algorithms
- Submatrix
- Theoretical computer science
- VLSI
- VLSI circuit
- SameAs
- 4iHVZ
- Complexidade de comunicação
- Complexité de la communication
- İletişim karmaşıklığı
- Kommunikationskomplexität
- m.0d9qw
- Q5154130
- Độ phức tạp truyền thông
- Коммуникационная сложность
- סיבוכיות תקשורת
- 通信複雑性
- Subject
- Category:Communication
- Category:Computational complexity theory
- Category:Quantum complexity theory
- WasDerivedFrom
- Communication complexity?oldid=1108502621&ns=0
- WikiPageLength
- 26060
- Wikipage page ID
- 50329
- Wikipage revision ID
- 1108502621
- WikiPageUsesTemplate
- Template:Cite book
- Template:Harvtxt
- Template:Mvar
- Template:Reflist
- Template:Short description
- Template:Tmath
- Template:Use American English
- Template:Val