Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 1, 1996 | public
Journal Article Open

Coding for interactive communication


Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol π be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction. We study the following question: if in fact the channel is noisy, what is the effect upon the number of transmissions needed in order to solve the computation problem reliably? Technologically this concern is motivated by the increasing importance of communication as a resource in computing, and by the tradeoff in communications equipment between bandwidth, reliability, and expense. We treat a model with random channel noise. We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slowdown. This is an analog for general, interactive protocols of Shannon's coding theorem, which deals only with data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are determined only one at a time, dynamically, in the course of the interaction. Instead, we describe a simulation protocol using a new kind of code, explicit tree codes.

Additional Information

© Copyright 1996 IEEE. Reprinted with permission. Manuscript received March 1, 1995; revised April 10, 1996. This research was conducted at MIT (see [26], [27] for preliminary presentations and related work) and at the University of California at Berkeley (see [28]). This work was supported at MIT under an ONR graduate fellowship, an MIT Applied Mathematics graduate fellowship, and under Grants NSF 8912586 CCR and AFOSR 89-0271. At Berkeley, this work was supported by NSF under a postdoctoral fellowship. The author wishes to thank his advisor M. Sipser whose oversight and encouragement in the early stages of this work were invaluable. For consultations and comments, the author also wishes to thank D. Abramovich, M. Blum, P. Elias, W. Evans, R. Gallager, W. Goddard, 0. Goldreich, M. Karchmer, R. Karp, C. Kenyon, D. Kleitman, M. Klugennan, N. Linial, M. Luby, M. Naor, Y. Peres, N. Pippenger, Y. Rabani, S. Rajagopalan, A. Sutherland, U. Vazirani, B. Velickovic, and D. Zuckerman. Finally, the author wishes to thank the Associate Editor, R. Cruz, and the anonymous referees, whose careful comments substantially improved the paper.


Files (193.3 kB)
Name Size Download all
193.3 kB Preview Download

Additional details

August 22, 2023
October 16, 2023