Can I read Optimal Las Vegas reduction from one-way set reconciliation to error correction on EtoBox?

Optimal Las Vegas reduction from one-way set reconciliation to error correction by Belazzougui, Djamal is a scholarly article available to read on EtoBox.

What is Optimal Las Vegas reduction from one-way set reconciliation to error correction about?

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 $[\sigma]$, where the first string contains $n$ non-zero entries. We would wish to answer to 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]$ and values are from $[\sigma]$ and usually $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 $\Theta(n)$ over an alphabet of size $2^{\Theta(\log\sigma+\log (u/n))}$. The additional running time incurred by the reducti

Author

Belazzougui, Djamal

Published

2015

Language

EN