This paper by Andrew Chi-Chih Yao explores the complexity of information exchange required for two processors to compute Boolean-valued functions. The problem is formulated as follows: two processors, \(P_1\) and \(P_2\), known only to each other integers \(i\) and \(j\) respectively, must determine the value of a Boolean function \(f(i, j)\) through a series of bit exchanges. The goal is to minimize the total number of bits exchanged, which is referred to as the "tw-way complexity" of \(f\), denoted as \(C(f; 1 \rightarrow 2)\). The paper introduces a deterministic model where the processors follow a specific algorithm to exchange bits, and defines the complexity in terms of the height of the decision tree representation of the algorithm. Yao proves that the tw-way complexity of any Boolean function is at least \(\log_4 d(f) - 2\), where \(d(f)\) is the minimum number of disjoint monochromatic rectangles needed to partition the domain and range of \(f\). For probabilistic models, the paper discusses two scenarios: one-way probabilistic communications and two-way probabilistic communications. In the one-way model, \(P_1\) sends a stochastic string to \(P_2\), and \(P_2\) decides the value of \(f\) with an error probability \(\epsilon\). The complexity in this model is shown to be approximately \(\log n - \log \log n - 2\) for random functions. In the two-way model, both processors can make stochastic moves, and the complexity is shown to be at least \(N(\log_2 \log_2 \text{row}(f) + \log_2 \log_2 \text{col}(f))\) for any function \(f\). The paper concludes with open questions, including the determination of the exact complexity for specific functions, the understanding of probabilistic models, and the extension to more than two processors. It also raises the question of whether computing the complexity \(C(f; 1 \rightarrow 2)\) is NP-complete.This paper by Andrew Chi-Chih Yao explores the complexity of information exchange required for two processors to compute Boolean-valued functions. The problem is formulated as follows: two processors, \(P_1\) and \(P_2\), known only to each other integers \(i\) and \(j\) respectively, must determine the value of a Boolean function \(f(i, j)\) through a series of bit exchanges. The goal is to minimize the total number of bits exchanged, which is referred to as the "tw-way complexity" of \(f\), denoted as \(C(f; 1 \rightarrow 2)\). The paper introduces a deterministic model where the processors follow a specific algorithm to exchange bits, and defines the complexity in terms of the height of the decision tree representation of the algorithm. Yao proves that the tw-way complexity of any Boolean function is at least \(\log_4 d(f) - 2\), where \(d(f)\) is the minimum number of disjoint monochromatic rectangles needed to partition the domain and range of \(f\). For probabilistic models, the paper discusses two scenarios: one-way probabilistic communications and two-way probabilistic communications. In the one-way model, \(P_1\) sends a stochastic string to \(P_2\), and \(P_2\) decides the value of \(f\) with an error probability \(\epsilon\). The complexity in this model is shown to be approximately \(\log n - \log \log n - 2\) for random functions. In the two-way model, both processors can make stochastic moves, and the complexity is shown to be at least \(N(\log_2 \log_2 \text{row}(f) + \log_2 \log_2 \text{col}(f))\) for any function \(f\). The paper concludes with open questions, including the determination of the exact complexity for specific functions, the understanding of probabilistic models, and the extension to more than two processors. It also raises the question of whether computing the complexity \(C(f; 1 \rightarrow 2)\) is NP-complete.