Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-042 | 6th April 2011 04:04

Efficiently Coding for Interactive Communication

RSS-Feed




Revision #1
Authors: Ankur Moitra
Accepted on: 6th April 2011 04:04
Downloads: 1060
Keywords: 


Abstract:

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. This protocol fails over a noisy channel with only exponentially small probability. However, this scheme is not computationally {\em efficient}: the running time to construct a good distance {\em tree code} (and perform encoding and decoding), which is the basis for the simulation, requires time exponential in the length of the protocol. Here, we give a computationally efficient simulation that achieves constant slow-down, and fails over a noisy channel with only polynomially small probability. Our protocol is deterministic and is based on a new type of code, which we call a {\em local tree code}. These codes can be regarded as an embedding of a tree code into a high-girth expander, so that locally these codes resemble tree codes, but are concisely represented and admit efficient encoding and decoding schemes (that succeed with high probability when communicating over a noisy channel).


Paper:

TR11-042 | 25th March 2011 01:41

Efficiently Coding for Interactive Communication





TR11-042
Authors: Ankur Moitra
Publication: 25th March 2011 01:55
Downloads: 1982
Keywords: 


Abstract:

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct a good distance {\em tree code} (and perform encoding and decoding), which is the basis for the simulation, requires time exponential in the length of the protocol. Here, we give the first computationally efficient simulation that achieves constant slow-down, and is robust to noise. In fact, our protocol is deterministic and is in part based on recent progress on constructive proofs of the general Lov\'asz Local Lemma. Prior to this work, the only known {\em efficient} simulation was the naive one based on retransmitting each bit in order to achieve reliability. Our approach is based on a new type of code, which we call a {\em local tree code}. These codes can be regarded as an embedding of a tree code into a high-girth expander, so that locally these codes resemble tree codes, but are concisely represented and admit efficient encoding and decoding schemes (that succeed with high probability when communicating over a noisy channel).



ISSN 1433-8092 | Imprint