Communication complexity

The communication complexity is a branch of complexity theory and is used to examine the question of how much communication to solve certain tasks is required, the input to multiple computers is distributed. The main focus is on the number of bits that have to be sent between the computers so that they can perform the task assigned to them. Communication complexity is a tool of theoretical computer science , especially when proving lower bounds for the resource requirements of calculations.

Differentiation from complexity theory

The goal of complexity theory is to estimate the minimum resources needed to solve algorithmic problems. The lower bounds proven so far are based on complexity theoretical hypotheses or refer to special scenarios such as the black box scenario.

The core ideas used to prove these lower bounds were filtered out and separated from the originally concrete application of the complexity theory in 1979 by Andrew C. Yao . This gave rise to the theory of communication complexity. Initially introduced as a cost measure for data exchange with parallel computers, communication complexity subsequently turned out to be an important aid for deriving lower bounds in VLSI chip design and circuit complexity.

Aspects and rationale

In electronic data processing , many aspects are viewed as a series of communication processes. Communication always takes place or is always necessary when two or more computers, components, systems or people have to solve a task together that neither of them can handle alone, for example because nobody alone has all the data or resources. In many cases there is obvious communication such as B. when looking for information from the Internet. Inquiries and answers are sent via an internet connection.

However, scenarios are also possible in which communication only takes place implicitly, such as B. by using a computer program . In this case the communication or the exchange of information takes place between different computer components.

Communication model

When calculating a function on a VLSI chip, the given chip area is divided into two areas. This gives each area part of the input. The two areas of the chip must exchange information so that the function can be calculated. If a lot of information has to be exchanged due to the properties of the function to be calculated, either a lot of computing time is required or the borderline between the two areas of the chip and thus the chip itself must be large.

Communication complexity is the number of bits that two processors (we call them Alice and Bob) have to exchange in order to jointly evaluate a function if each processor originally knows one of the arguments or . ${\ displaystyle F (x, y)}$ ${\ displaystyle x}$ ${\ displaystyle y}$

Alice is only known from the input , while Bob knows. Both are given unlimited computing capacity internally. The only essential aspect is communication. Alice and Bob agree in advance on a protocol that dictates what to do for each situation. ${\ displaystyle (x, y)}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle P}$

If the sequence is the bits already communicated, then Alice and Bob know . It must now be clear for both of them who is sending the next message, whereby the message sent may only depend on local information. At the end of the communication, Alice and Bob should know. The length of the protocol for input is the number of bits communicated between Alice and Bob. The number of bits sent to calculate the number of bits sent is considered to be the communication complexity of the protocol when it is entered. ${\ displaystyle m}$ ${\ displaystyle (x, m)}$ ${\ displaystyle (y, m)}$ ${\ displaystyle F (x, y)}$ ${\ displaystyle P}$ ${\ displaystyle (x, y)}$ ${\ displaystyle F (x, y)}$ ${\ displaystyle P}$ ${\ displaystyle (x, y)}$

The communication complexity of a function is the length of the shortest protocol.

AT² barriers on a VLSI chip

The chip design today, as then, is determined by accommodating as much logic as possible on a small chip, which reduces costs. On the other hand, the chip should calculate a result as quickly as possible. For VLSI designers, lower bounds in terms of computing time and the size of the chip were therefore of great interest. For the discrete Fourier transformation, for example B. prove that AT²> n2 16. Refers here to the surface of the chip, the required clock cycles and the length of the binary input. This calculation gave the so-called AT² limits. ${\ displaystyle A}$ ${\ displaystyle T}$ ${\ displaystyle n}$

AT² barriers are not only limited to the VLSI design, but can also be used for many other function calculations.

literature

E. Kushilevitz and N. Nisan - Communication Complexity - Cambridge University Press 1997 (textbook, 189 pages) - ISBN 0-521-56067-5
N. Nisan and A. Wigderson - Rounds in Communication Complexity Revisited - SIAM Journal on Computing, Vol. 22 (1), pages 211-219, 19932