论文标题
改进的素描算法用于编辑距离
An Improved Sketching Algorithm for Edit Distance
论文作者
论文摘要
我们为编辑距离的同时草图复杂性提供了改进的上限。考虑两个各方，带有输入$ x \inς^n $的爱丽丝和带有输入$ y \inς^n $的鲍勃，它们共享公共随机性，并承诺在两个字符串之间的编辑距离$ \ mathsf {ed}（x，y）$之间的两个字符串之间是最多给出的值$ k $。爱丽丝必须发送$ sx $的消息，鲍勃必须向第三方查理发送$ sy $，后者不知道投入，但具有相同的公共随机性，并且也知道$ k $。查理必须输出$ \ mathsf {ed}（x，y）$，以及$ \ mathsf {ed}（x，y）$ edits的序列，将$ x $转换为$ y $所需。目标是最大程度地减少发送消息的长度$ | sx |，| sy | $。 Belazzougui和Zhang（Focs 2016）的协议，基于Chakraborty，Goldenberg和Koucký（STOC 2016）的随机步行方法，达到了最大消息长度$ \ tilde o（k^8）$ bits $ bits $ bits $ bits $ \ tilde o（\ cdot o（\ cdot）$ hides $ hide $ \ blog \ nlog \ \ \ \ contoly;在这项工作中，我们以Belazzougui和Zhang的协议为基础，并提供了改进的分析，表明其构造的稍作修改实现了$ \ tilde o（k^3）$的界限。
We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input $x\inΣ^n$ and Bob with input $y\inΣ^n$, that share public randomness and are given a promise that the edit distance $\mathsf{ed}(x,y)$ between their two strings is at most some given value $k$. Alice must send a message $sx$ and Bob must send $sy$ to a third party Charlie, who does not know the inputs but shares the same public randomness and also knows $k$. Charlie must output $\mathsf{ed}(x,y)$ precisely as well as a sequence of $\mathsf{ed}(x,y)$ edits required to transform $x$ into $y$. The goal is to minimize the lengths $|sx|, |sy|$ of the messages sent. The protocol of Belazzougui and Zhang (FOCS 2016), building upon the random walk method of Chakraborty, Goldenberg, and Koucký (STOC 2016), achieves a maximum message length of $\tilde O(k^8)$ bits, where $\tilde O(\cdot)$ hides $\mathrm{poly}(\log n)$ factors. In this work we build upon Belazzougui and Zhang's protocol and provide an improved analysis demonstrating that a slight modification of their construction achieves a bound of $\tilde O(k^3)$.
