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 others 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 $nll 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(logsigma+log (u/n))}$. The additional running time incurred by the reduction is linear randomized for player $A$ and linear deterministic for player $B$, but the correction works with certainty. When using the popular Reed-Solomon codes, the reduction gives a protocol that transmits $O(k(log u+logsigma))$ bits and runs in time $O(ncdotmathrm{polylog}(n)(log u+logsigma))$ for all values of $k$. The time is randomized for player $A$ (encoding time) and deterministic for player $C$ (decoding time). The space is optimal whenever $kleq (usigma)^{1-Omega(1)}$.
Download