Optimal Las Vegas reduction from one-way set reconciliation to error correction
| dc.contributor.author | Belazzougui, Djamal | |
| dc.date.accessioned | 2016-10-02T14:29:30Z | |
| dc.date.available | 2016-10-02T14:29:30Z | |
| dc.date.issued | 2016-03-28 | |
| dc.description.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)}. | fr_FR |
| dc.identifier.issn | 0304-3975 | fr_FR |
| dc.identifier.uri | http://dl.cerist.dz/handle/CERIST/830 | |
| dc.publisher | Springer Varlag | fr_FR |
| dc.relation.ispartofseries | Theoretical Computer Science;621 | |
| dc.relation.pages | 14-21 | fr_FR |
| dc.structure | Analyse et modélisation de systèmes pour l'aide à la décision | fr_FR |
| dc.subject | Set reconciliation | fr_FR |
| dc.subject | Hamming distance | fr_FR |
| dc.subject | Reduction | fr_FR |
| dc.subject | Error correcting codes | fr_FR |
| dc.subject | Las Vegas | fr_FR |
| dc.subject | Hashing | fr_FR |
| dc.title | Optimal Las Vegas reduction from one-way set reconciliation to error correction | fr_FR |
| dc.type | Article |