Golan, Shay ;
Kociumaka, Tomasz ;
Kopelowitz, Tsvi ;
Porat, Ely ;
Uznański, Przemysław
Improved Circular kMismatch Sketches
Abstract
The shift distance sh(S₁,S₂) between two strings S₁ and S₂ of the same length is defined as the minimum Hamming distance between S₁ and any rotation (cyclic shift) of S₂. We study the problem of sketching the shift distance, which is the following communication complexity problem: Strings S₁ and S₂ of length n are given to two identical players (encoders), who independently compute sketches (summaries) sk(S₁) and sk(S₂), respectively, so that upon receiving the two sketches, a third player (decoder) is able to compute (or approximate) sh(S₁,S₂) with high probability.
This paper primarily focuses on the more general kmismatch version of the problem, where the decoder is allowed to declare a failure if sh(S₁,S₂) > k, where k is a parameter known to all parties. Andoni et al. (STOC'13) introduced exact circular kmismatch sketches of size Õ(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 (nonlinear) exact circular kmismatch sketch of size Õ(k); this size matches communicationcomplexity lower bounds. We also design (1± ε)approximate circular kmismatch sketch of size Õ(min(ε^{2}√k, ε^{1.5}√n)), which improves upon an Õ(ε^{2}√n)size sketch of Crouch and McGregor (APPROX'11).
BibTeX  Entry
@InProceedings{golan_et_al:LIPIcs:2020:12649,
author = {Shay Golan and Tomasz Kociumaka and Tsvi Kopelowitz and Ely Porat and Przemys{\l}aw Uznański},
title = {{Improved Circular kMismatch Sketches}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {46:146:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12649},
URN = {urn:nbn:de:0030drops126492},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.46},
annote = {Keywords: Hamming distance, kmismatch, sketches, rotation, cyclic shift, communication complexity}
}
11.08.2020
Keywords: 

Hamming distance, kmismatch, sketches, rotation, cyclic shift, communication complexity 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 