Efficient and Explicit Coding for Interactive Communication

We revisit the problem of reliable interactive communication over a noisy channel, and obtain the first fully explicit (randomized) efficient constant-rate emulation procedure for reliable interactive communication. Our protocol works for any discrete memory less noisy channel with constant capacity, and fails with exponentially small probability in the total length of the protocol. Following a work by Schulman [Schulman 1993] our simulation uses a tree-code, yet as opposed to the non-constructive absolute tree-code used by Schulman, we introduce a relaxation in the notion of goodness for a tree code and define a potent tree code. This relaxation allows us to construct an explicit emulation procedure for any two-party protocol. Our results also extend to the case of interactive multiparty communication. We show that a randomly generated tree code (with suitable constant alphabet size) is an efficiently decodable potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result by means of epsilon-biased distributions using only O(N) random bits, where N is the depth of the tree.

Authors

• Ran Gelles
• Ankur Moitra
• Amit Sahai

Keywords

• Protocols
• Emulation
• Hamming distance
• Noise measurement
• Channel capacity
• Channel coding
• Communication Problems
• Small Probability
• Tree Depth
• Reliable Communication
• Noisy Channels
• Random Bits
• Coding Tree
• Explicit Procedure
• Common Ancestor
• Error Probability
• Probability Of Failure
• Original Protocol
• Subtree
• Small Trees
• Simulation Procedure
• Forward Error Correction
• Decoding Process
• Lowest Common Ancestor
• Explicit Construction
• Fractional Error
• Decoding Procedure
• Divergent Paths
• Efficient Decoding
• Decoding Error
• Input Symbols
• tree codes
• interactive communication with noise
• derandomization