Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding

We study coding schemes for error correction in interactive communications. Such interactive coding schemes simulate any n-round interactive protocol using N rounds over an adversarial channel that corrupts up to ρN transmissions. Important performance measures for a coding scheme are its maximum tolerable error rate ρ, communication complexity N, and computational complexity. We give the first coding scheme for the standard setting which performs optimally in all three measures: Our randomized non-adaptive coding scheme has a near-linear computational complexity and tolerates any error rate δ 1.

Authors

• Mohsen Ghaffari 0001
• Bernhard Haeupler

Keywords

• Encoding
• Decoding
• Protocols
• Error analysis
• Computational complexity
• Error correction codes
• Interactive
• Error Rate
• List Decoding
• Optimal Error Rate
• Computational Efficiency
• Complex Communication
• Important Performance Measure
• Probability Of Failure
• Canonical Form
• Codeword
• Binary Tree
• Forward Error Correction
• Beginning Of Each Block
• List Size
• Search Phase
• Common Path
• Communication Rounds
• Part Of Joint
• Fractional Error
• Correct Path
• Decoding Procedure
• Alphabet Size
• Coding
• Interactive Communication
• Efficiency
• Error-Rate
• List-Decoding