Interactive and Amortized Communication – An Information Theoretic Perspective
summary
Examines concrete gaps: the indexing (league) example shows one-way needs ~log n bits while a two-message protocol sends one index plus a single bit so communication drops to about log log n, an exponential improvement. Proves two messages are within a constant factor (≈4) of optimal and gives worst-case bounds for t-insertions syncing (one insertion hits the conditional-entropy benchmark, two insertions lie between that and twice it; three-message interactive protocols reach the benchmark up to logarithmic overhead). Uses mutual information, conditional graph entropy and rate-distortion style tools to equate information complexity with amortized communication and to obtain diminishing block-error guarantees.
AI-written summary · about