Optimal Las Vegas reduction from one-way set reconciliation to error correction

详细信息    查看全文

• 作者：Djamal Belazzougui ; ^{dbelazzougui@cerist.dz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Set reconciliation ; Hamming distance ; Reduction ; Error correcting codes ; Las Vegas ; Hashing
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：28 March 2016
• 年：2016
• 卷：621
• 期：Complete
• 页码：14-21
• 全文大小：339 K

文摘

Suppose we have two players A and C, where player A   has a string s[0..u−1]$s[0..u-1]$ and player C   has a string t[0..u−1]$t[0..u-1]$ and none of the two players knows the other's string.

Assume that s and t   are both over an integer alphabet [σ]=[0,σ−1]$[\sigma ]=[0,\sigma -1]$, where the first string contains n non-zero entries. We would wish to answer the following basic question. Assuming that s and t differ in at most k positions, how many bits does player A need to send to player C so that he can recover s with certainty? Further, how much time does player A need to spend to compute the sent bits and how much time does player C need to recover the string s? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of n   key-value pairs, where keys are from the universe [u]$[u]$ and values are from [σ]$[\sigma ]$ and usually n≪u$n\ll u$.

In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of k   errors for strings of length Θ(n)$\mathrm{\Theta }(n)$ over an alphabet of size 2^{Θ(log⁡σ+log⁡(u/n))}$2^{\mathrm{\Theta }(\log \sigma +\log (u/n))}$.

The additional running time incurred by the reduction is linear expected (randomized) for player A and linear worst-case (deterministic) for player C  , but the correction works with certainty. When using the popular Reed–Solomon codes, the reduction gives a protocol that transmits O(k(log⁡u+log⁡σ))$O(k(\log u+\log \sigma ))$ bits and runs in time O(n⋅polylog(n)(log⁡u+log⁡σ))$O(n\cdot \text{polylog}(n)(\log u+\log \sigma ))$ for all values of k. The time is expected for player A (encoding time) and worst-case for player C   (decoding time). The message size is optimal whenever k≤(uσ)^1−Ω(1)$k\le {(u\sigma )}^{1-\mathrm{\Omega }(1)}$.