摘要：We provide improved upper bounds for the simultaneous sketching complexity of edit distance. Consider two parties, Alice with input x â^^ Σ⿠and Bob with input y â^^ Σâ¿, that share public randomness and are given a promise that the edit distance 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 ed(x,y) precisely as well as a sequence of 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 Ã.(kâ¸) bits, where Ã.(â<.) hides 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 Ã.(k³).
