论文标题
有效的文档交换和错误纠正非对称信息的代码
Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
论文作者
论文摘要
我们研究了交流，文件交换（DE）和错误纠正代码（ECC）的两个基本问题。在第一个问题中，两个政党持有两个弦乐，一个政党试图通过交流来学习另一方的字符串。在第二个问题中，一个方试图通过添加一些冗余信息来保护该消息，试图通过嘈杂的渠道向另一方发送消息。这两个问题的两个重要目标是最大程度地减少通信复杂性或冗余，并设计有效的协议或代码。 这两个问题已经进行了广泛的研究。在本文中，我们研究了不对称的部分信息是否可以帮助这两个问题。我们专注于锤击距离/错误的情况，不对称的部分信息是由一个具有不相交子集的向量$ \ vec {s} =（s_1，\ cdots，s_t，s_t）$的方向建模的距离/错误最多为$ k_i $。我们在此模型中同时建立了下限和上限，并提供有效的随机结构，以实现$ \ min \ lbrace o（t^2），o \ left（（（\ log \ log \ log \ log n）^2 \ right）\ rbrace $ factor在最佳内，几乎是线性运行时间。 我们进一步显示了上述文档交换问题与编辑距离下的文档交换问题之间的连接，并使用我们的技术提供有效的随机协议，具有最佳的通信复杂性，而后者则提供了\ emph {指数}小错误。这改善了Haeupler \ cite {Haeupler2018Optimal}（focs'19）的结果，并由Belazzougui和Zhang \ cite {Belazzouguiz16}（focs'16）和belazzougui和zhang \ cite。我们的技术基于Sipser和Spielman \ cite {Sipser1996expander}对著名扩展器代码的概括，这可能具有独立的利益。
We study two fundamental problems in communication, Document Exchange (DE) and Error Correcting Code (ECC). In the first problem, two parties hold two strings, and one party tries to learn the other party's string through communication. In the second problem, one party tries to send a message to another party through a noisy channel, by adding some redundant information to protect the message. Two important goals in both problems are to minimize the communication complexity or redundancy, and to design efficient protocols or codes. Both problems have been studied extensively. In this paper we study whether asymmetric partial information can help in these two problems. We focus on the case of Hamming distance/errors, and the asymmetric partial information is modeled by one party having a vector of disjoint subsets $\vec{S}=(S_1, \cdots, S_t)$ of indices and a vector of integers $\vec{k}=(k_1, \cdots, k_t)$, such that in each $S_i$ the Hamming distance/errors is at most $k_i$. We establish both lower bounds and upper bounds in this model, and provide efficient randomized constructions that achieve a $\min\lbrace O(t^2), O\left((\log \log n)^2\right) \rbrace $ factor within the optimum, with almost linear running time. We further show a connection between the above document exchange problem and the problem of document exchange under edit distance, and use our techniques to give an efficient randomized protocol with optimal communication complexity and \emph{exponentially} small error for the latter. This improves the previous result by Haeupler \cite{haeupler2018optimal} (FOCS'19) and that by Belazzougui and Zhang \cite{BelazzouguiZ16} (FOCS'16). Our techniques are based on a generalization of the celebrated expander codes by Sipser and Spielman \cite{sipser1996expander}, which may be of independent interests.
