期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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).
