Optimal Las Vegas reduction from one-way set reconciliation to error correction

详细信息    查看全文

• 作者：Djamal Belazzougui ; ^{dbelazzougui@cerist.dz" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Set reconciliation ; Hamming distance ; Reduction ; Error correcting codes ; Las Vegas ; Hashing
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：28 March 2016
• 年：2016
• 卷：621
• 期：Complete
• 页码：14-21
• 全文大小：339 K

文摘

Suppose we have two players A and C, where player A   has a string id="mmlsi1" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si1.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=7a41764be94927f17c38ef62fb24b85c" title="Click to view the MathML source">s[0..u−1]iner hidden">i1.gif" overflow="scroll">i>si>[0..i>ui>−1] and player C   has a string id="mmlsi2" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si2.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=b6381ee22535f15a8761547a1dd60dab" title="Click to view the MathML source">t[0..u−1]iner hidden">i2.gif" overflow="scroll">i>ti>[0..i>ui>−1] and none of the two players knows the other's string.

id="sp0020">Assume that s and t   are both over an integer alphabet id="mmlsi3" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si3.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=801209350405f9e89f0324aed94ffee7" title="Click to view the MathML source">[σ]=[0,σ−1]iner hidden">i3.gif" overflow="scroll">[i>σi>]=[0,i>σi>−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 id="mmlsi4" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si4.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=dc28862d56a03e0bd53cd8b5e8b925c7" title="Click to view the MathML source">[u]iner hidden">i4.gif" overflow="scroll">[i>ui>] and values are from id="mmlsi5" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si5.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=3453625dc3567093092ed4c7346f96a3" title="Click to view the MathML source">[σ]iner hidden">i5.gif" overflow="scroll">[i>σi>] and usually id="mmlsi6" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si6.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=4c161c0505588d7c8eb4cf122ad7aaa8" title="Click to view the MathML source">n≪uiner hidden">i6.gif" overflow="scroll">i>ni>≪i>ui>.

id="sp0030">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 id="mmlsi49" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si49.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=1b21cc98db235f22f2ab533eafca6d43" title="Click to view the MathML source">Θ(n)iner hidden">i49.gif" overflow="scroll">i mathvariant="normal">Θi>(i>ni>) over an alphabet of size id="mmlsi8" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si8.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=032d059f0ec1e2a1f27fdf6b9f082c1d" title="Click to view the MathML source">2^{Θ(log⁡σ+log⁡(u/n))}iner hidden">i8.gif" overflow="scroll">2i mathvariant="normal">Θi>(i mathvariant="normal">logi>⁡i>σi>+i mathvariant="normal">logi>⁡(i>ui>/i>ni>)).

id="sp0040">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 id="mmlsi9" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si9.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=d0bbadd80455809414220b614644bcc7" title="Click to view the MathML source">O(k(log⁡u+log⁡σ))iner hidden">i9.gif" overflow="scroll">i>Oi>(i>ki>(i mathvariant="normal">logi>⁡i>ui>+i mathvariant="normal">logi>⁡i>σi>)) bits and runs in time id="mmlsi10" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si10.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=035e32da43395b277b6adf74d3bcf11b" title="Click to view the MathML source">O(n⋅polylog(n)(log⁡u+log⁡σ))iner hidden">i10.gif" overflow="scroll">i>Oi>(i>ni>⋅polylog(i>ni>)(i mathvariant="normal">logi>⁡i>ui>+i mathvariant="normal">logi>⁡i>σi>)) 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 id="mmlsi11" class="mathmlsrc">ixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000438&_mathId=si11.gif&_user=111111111&_pii=S0304397516000438&_rdoc=1&_issn=03043975&md5=3fda94eab70e03057f66f4046dcd3dfc" title="Click to view the MathML source">k≤(uσ)^{1−Ω(1)}iner hidden">i11.gif" overflow="scroll">i>ki>≤(i>ui>i>σi>)1−i mathvariant="normal">Ωi>(1).