Communication complexity
Communication complexity is a field that examines how to efficiently transfer information between parties while minimizing the amount of communication required. It is particularly relevant in contexts such as computer systems optimization, cryptology, and project management. Introduced by Chinese American computer scientist Andrew Chi-Chih Yao in 1979, this concept explores scenarios where two individuals, often referred to as "Alice" and "Bob," possess complementary pieces of information needed to solve a problem. Rather than simply sharing all information directly, the focus is on finding creative alternatives to collaborate effectively while maintaining security.
The field is crucial for enhancing data protection, as it helps in determining how much information can be shared without compromising sensitive data. Techniques within communication complexity often involve using public and private strings of information, enabling parties to exchange data securely. Additionally, the use of an oracle—a third information source—can facilitate this transfer. Applications of communication complexity extend to areas such as game theory and circuit complexity, where understanding interactions and outcomes is essential. This study not only aids in optimizing communication protocols but also plays a significant role in safeguarding information in various technological fields.
On this Page
Communication complexity
Communication complexity is a field of study that focuses on ways to complete an information transfer task using the least possible amount of communication. It is a factor in the optimization of computer systems and networks, in cryptology, and in project management. In this instance, complexity is not defined by the amount of computer calculations or computer memory that it takes to convey information. Instead, the focus is on determining how much interaction between two or more communication sources is necessary to share the required information.
Overview
Chinese American computer scientist Andrew Chi-Chih Yao first proposed communication complexity as a theoretical question. In 1979, Yao investigated the ways that two individuals could solve an equation when one individual had half of the necessary information, and the other individual had the other half. Although one individual could simply give all the information to the other, Yao was interested in finding creative ways to share the information.
Research scientists often refer to these individuals as "Alice" and "Bob," using names to stand in for the a and b variables often used in equations. Computer cryptography and security experts from RSA Security first used Alice and Bob in 1978 as a way to turn abstract variables into something easier to grasp. Yao's theoretical problem proposed that Alice knew one piece of the equation and Bob knew the other and sought alternatives other than direct transfer of the information.
The concept particularly interested people involved in cryptology, or the use of codes, passwords, and other secret methods of sharing information and maintaining the security of computer systems. In these situations, completing tasks while sharing the least possible amount of information enhanced professionals' ability to protect sensitive data and systems.
Under the communication complexity concept, none of the individuals (or computers, computer networks, etc.) have all the information, and none of them knows what information any of the other individuals (or computers, computer networks, etc.) has at the start. Each time a bit of information is shared, the matrix containing the pool of information that is known by more than one individual grows. At the same time, the matrix of information that is known by only one individual shrinks. This aspect is of the most concern to those seeking to protect secrecy and security in systems and programs.
One of the ways this information is shared is through public and private strings of information. In Yao's example, Alice would have one private string, and Bob would have another, and both would have the same public string. Known as a randomized protocol, this method of transferring information works in a way similar to solving a code when both have a decoding key. Yao's communication complexity concept also allowed for other ways to convey the information, including the use of a third information source called an oracle that could help with the transfer.
This concept has a number of applications. These include determining the lowest element of a given set of information (known as the lower bound) and determining the complexity of certain circuits and proofs. It is also important to game theory, or the theory of determining potential outcomes in situations such as social interactions and war, where one entity's actions are dependent on the outcome of another's actions.
Bibliography
"Approximation - Edexcel: Upper and Lower Bounds." BBC Bitesize, www.bbc.co.uk/schools/gcsebitesize/maths/number/roundestimaterev5.shtml. Accessed 18 Dec. 2024.
Braverman, Mark. "Introduction to Communication Complexity." Princeton University, 7 Nov. 2011, www.cs.princeton.edu/courses/archive/fall11/cos597D/L13.pdf. Accessed 18 Dec. 2024.
Hayes, Adam. "Game Theory: A Comprehensive Guide." Investopedia, 27 June 2024, www.investopedia.com/terms/g/gametheory.asp. Accessed 18 Dec. 2024.
O'Donnell, Ryan. "Communication Complexity." Carnegie Mellon University, 11 Nov. 2013, www.cs.cmu.edu/~odonnell/toolkit13/lecture19.pdf. Accessed 18 Dec. 2024.
Pitassi, Toniann. "Foundation of Communication Complexity." University of Toronto, 2014, www.cs.toronto.edu/~toni/Courses/CommComplexity2/Lectures/lecture5.pdf. Accessed 18 Dec. 2024.
Razborov, Alexander A. "Communication Complexity." University of Chicago, people.cs.uchicago.edu/~razborov/files/cc.pdf. Accessed 18 Dec. 2024.
Roughgarden, Tim. "Communication Complexity (for Algorithm Designers)." Stanford University, 2015, theory.stanford.edu/~tim/w15/l/w15.pdf. Accessed 18 Dec. 2024.
William L. Hosch. “Andrew Chi-Chih Yao.” Britannica Biographies, May 2024, p. 1. EBSCOhost, search.ebscohost.com/login.aspx?direct=true&db=apr&AN=47329418&site=ehost-live. Accessed 18 Dec. 2024.