WORST-CASE INTERACTIVE COMMUNICATION .1. 2 MESSAGES ARE ALMOST OPTIMAL

X and Y are random variables. Person [Formula omited] knows X, Person [Formula omited] knows Y and both know the joint probability distribution of (X.Y). Using a predetermined protocol, they communicate over a binary, error-free, channel in order for [Formula omited] to learn X. [Formula omited] may or may not learn Y. How many information bits must be transmitted (by both persons) in the worst case if only m messages are allowed? [Formula omited] is the number of bits required when at most one message is allowed, necessarily from [Formula omited] to [Formula omited]. [Formula omited] is the number of bits required when at most two messages are permitted: Ptransmits a message to [Formula omited] then [Formula omited] responds with a message to [Formula omited]. [Formula omited] is the number of bits required when communication is unrestricted: [Formula omited] and [Formula omited] can communicate back and forth. The maximum reduction in communication achievable via interaction is almost logarithmic. For all (X,Y) pairs, [Formula omited], whereas, for a class of (X,Y) pairs, [Formula omited]. Therefore, [Formula omited] can be exponentially larger than [Formula omited]. Yet [Formula omited] cannot. With just two messages, the number of bits required is at most four times larger than the minimum: for all (X,Y) pairs, [Formula omited]. This contrasts with communication complexity where, for every m, the number of bits required with m messages can be almost exponentially larger than needed with m +1 messages. Surprisingly, for almost all sparse (X,Y) pairs, [Formula omited] who wants to say nothing must transmit almost all the bits to achieve the minimum number: [Formula omited]. The number of bits transmitted by [Formula omited] can be appreciably reduced only if [Formula omited] transmits exponentially more than [Formula omited] bits. If the communicators can tolerate ∊ probability of [Formula omited] not knowing the correct value of × and if randomized protocols are allowed then [Formula omited] bits suffice even without interaction. © 1990 IEEE