论文标题
改进的圆形$ k $ -mismatch草图
Improved Circular $k$-Mismatch Sketches
论文作者
论文摘要
两个字符串之间的移位距离$ \ MATHSF {SHSF {SHSF {S_1，S_2）$相同长度的$ S_1 $和$ S_2 $定义为$ S_1 $和任何旋转（环状移动）$ s_2 $之间的最小锤击距离。我们研究了素描轮班距离的问题，这是以下沟通复杂性问题：串联$ s_1 $和$ s_2 $长度$ n $的长度$ n $给出了两个相同的播放器（编码器），他们独立地计算草图（摘要）$ \ mathtt {sk} {sk}（s_1）$和$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ （解码器）能够以高概率计算（或近似）$ \ mathsf {sh}（s_1，s_2）$。 本文主要关注该问题的更通用的$ k $ -mismatch版本，其中允许解码器声明失败，如果$ \ mathsf {sh}（s_1，s_1，s_2）> k $，其中$ k $是所有各方都知道的参数。 Andoni等。 （stoc'13）引入了$ \ widetilde {o}（k+d（n））$的精确循环$ k $ -mismatch草图，其中$ d（n）$是$ n $的除数的数量。 Andoni等。还表明它们的草图大小在线性同构草图的类别中是最佳的。 我们通过设计（非线性）确切的圆形$ k $ -mismatch尺寸$ \ widetilde {o}（k）$的（k）$的（非线性）圆形$ k $ -mismatch草图来避免这种下限;这种尺寸与通信复杂性的下限相匹配。我们还设计$（1 \ pm \ varepsilon）$ - 近似圆形$ k $ -mismismatch大小$ \ widetilde {o}（\ min（\ varepsilon^{ - 2} \ sqrt { - 2} \ sqrt {k}，\ varepsilon^repsilon^{ - 1.5} $ \ widetilde {o}（\ varepsilon^{ - 2} \ sqrt {n}）$ - Crouch和McGregor的大小草图（大约11）。
The shift distance $\mathsf{sh}(S_1,S_2)$ between two strings $S_1$ and $S_2$ of the same length is defined as the minimum Hamming distance between $S_1$ and any rotation (cyclic shift) of $S_2$. We study the problem of sketching the shift distance, which is the following communication complexity problem: Strings $S_1$ and $S_2$ of length $n$ are given to two identical players (encoders), who independently compute sketches (summaries) $\mathtt{sk}(S_1)$ and $\mathtt{sk}(S_2)$, respectively, so that upon receiving the two sketches, a third player (decoder) is able to compute (or approximate) $\mathsf{sh}(S_1,S_2)$ with high probability. This paper primarily focuses on the more general $k$-mismatch version of the problem, where the decoder is allowed to declare a failure if $\mathsf{sh}(S_1,S_2)>k$, where $k$ is a parameter known to all parties. Andoni et al. (STOC'13) introduced exact circular $k$-mismatch sketches of size $\widetilde{O}(k+D(n))$, where $D(n)$ is the number of divisors of $n$. Andoni et al. also showed that their sketch size is optimal in the class of linear homomorphic sketches. We circumvent this lower bound by designing a (non-linear) exact circular $k$-mismatch sketch of size $\widetilde{O}(k)$; this size matches communication-complexity lower bounds. We also design $(1\pm \varepsilon)$-approximate circular $k$-mismatch sketch of size $\widetilde{O}(\min(\varepsilon^{-2}\sqrt{k}, \varepsilon^{-1.5}\sqrt{n}))$, which improves upon an $\widetilde{O}(\varepsilon^{-2}\sqrt{n})$-size sketch of Crouch and McGregor (APPROX'11).
