کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437456 | 690144 | 2016 | 8 صفحه PDF | دانلود رایگان |
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][σ]=[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][u] and values are from [σ][σ] and usually n≪un≪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)Θ(n) over an alphabet of size 2Θ(logσ+log(u/n))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(logu+logσ))O(k(logu+logσ)) bits and runs in time O(n⋅polylog(n)(logu+logσ))O(n⋅polylog(n)(logu+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)k≤(uσ)1−Ω(1).
Journal: Theoretical Computer Science - Volume 621, 28 March 2016, Pages 14–21