Optimal Las Vegas reduction from one-way set reconciliation to error correction
Loading...
Date
2016-03-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer Varlag
Abstract
Suppose we have two players A and C, where player A has a string s[0..u−1] and player C has a string 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], 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]=[0,u-1] and values are from [σ] and usually n ≪ 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) over an alphabet of size 2^{Θ(log σ+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 σ)) bits and runs in time O(n⋅polylog(n)(log u+log σ)) 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)}.
Description
Keywords
Set reconciliation, Hamming distance, Reduction, Error correcting codes, Las Vegas, Hashing