This paper explores the information exchange required for two processors to compute Boolean-valued functions. The problem involves two processors, P1 and P2, who know values i and j respectively, and must determine f(i,j) by exchanging bits. The goal is to find the minimum number of bits needed for this computation. The paper presents a deterministic model where processors exchange bits in a structured manner, and introduces the concept of f-monochromatic rectangles and k-decompositions to analyze the complexity of functions. The paper also discusses probabilistic models, where processors can use stochastic moves and allow for a small error probability. It introduces one-way and two-way probabilistic communication models, and analyzes their complexities. For example, in the one-way probabilistic model, the complexity of a random function is shown to be of order log n. In the two-way probabilistic model, the complexity is shown to improve logarithmically over deterministic one-way communication. The paper proves several theorems, including that the deterministic two-way complexity of a function is at least log d(f) - 2, where d(f) is the minimum number of f-monochromatic rectangles needed to partition the function. It also shows that for functions with planar decompositions, the complexity can be bounded by a logarithmic function of the number of rectangles. The paper concludes with open questions, including the determination of the exact complexity for specific functions and the NP-completeness of computing the complexity of a function. The results provide insights into the information exchange required for distributed computations and highlight the differences between deterministic and probabilistic models.This paper explores the information exchange required for two processors to compute Boolean-valued functions. The problem involves two processors, P1 and P2, who know values i and j respectively, and must determine f(i,j) by exchanging bits. The goal is to find the minimum number of bits needed for this computation. The paper presents a deterministic model where processors exchange bits in a structured manner, and introduces the concept of f-monochromatic rectangles and k-decompositions to analyze the complexity of functions. The paper also discusses probabilistic models, where processors can use stochastic moves and allow for a small error probability. It introduces one-way and two-way probabilistic communication models, and analyzes their complexities. For example, in the one-way probabilistic model, the complexity of a random function is shown to be of order log n. In the two-way probabilistic model, the complexity is shown to improve logarithmically over deterministic one-way communication. The paper proves several theorems, including that the deterministic two-way complexity of a function is at least log d(f) - 2, where d(f) is the minimum number of f-monochromatic rectangles needed to partition the function. It also shows that for functions with planar decompositions, the complexity can be bounded by a logarithmic function of the number of rectangles. The paper concludes with open questions, including the determination of the exact complexity for specific functions and the NP-completeness of computing the complexity of a function. The results provide insights into the information exchange required for distributed computations and highlight the differences between deterministic and probabilistic models.