A theoretical protocol described in an arXiv preprint could let two parties reconcile strings they hold separately while tying the amount of data they exchange to how different the strings are. In the paper’s main theorem, the IBLT-chunking algorithm determines the other party’s string in O(n) time and uses O(k log^3 n) bits, with probability at least 1 - 1/η. The guarantee is stated for n log n < η ≤ n^c, with c > 1.
Here, edit distance is a measure of how many changes separate two strings. The result is designed for strings of length Θ(n) over an alphabet of size O(n), held by Alice and Bob, with k serving as an a-priori-known upper bound on their edit distance. Those conditions define the input setting for which the theorem gives its bound.
The theorem keeps the two resource measures distinct. Its local running-time bound is linear in n, while its communication bound depends on k, the distance limit known to the parties, as well as logarithmic factors in n. If k is not known in advance, the paper states that the same result can be obtained with O(n log k) time overhead.
Breaking strings into comparable pieces
The protocol starts with locally consistent parsing, which divides each string into contiguous substring chunks. It places those chunks in parsing sets across a hierarchy with r ≤ log_2 n levels. Across the hierarchy, the total size of all parsing sets and hash functions is O(n).
To compare the sets, the protocol creates invertible Bloom lookup tables, or IBLTs, for the parsing sets. Bob can use the IBLTs to recover their elements with high probability. The protocol uses independent randomness for perfect hashing, block-boundary detection, chunk checksums and IBLT hashing.
The parsing analysis also gives a bound on how much one change can affect the representation. A single edit in X can alter at most 4 log_2 n elements in the corresponding sets A_i.
The IBLTs have a separate decoding guarantee. For the stated parameters, the analysis says that peeling at most d stored elements succeeds with probability at least 1 - 1/n^(c/2 - 1) when c ≥ 4. This is a probability bound for an internal decoding step, not a measured rate from a test.
The limits of the guarantee
The paper’s central comparison is stated in asymptotic terms. The authors describe the method as an improvement on an IBLT-based technique from their recent paper, while the theorem here gives the O(n) time and O(k log^3 n) bit bounds under its stated conditions.
The conclusion adds a separate representation result for repetitive strings. It states that the grammar representation has size O(γ log(n/γ)), where γ is the size of the string’s smallest attractor. This grammar bound is presented alongside the reconciliation result, not as a replacement for it.
The main theorem’s boundaries remain important when reading the headline figures. It is stated for strings of length Θ(n), an alphabet of size O(n), and an a-priori-known upper bound k. When that upper bound is unavailable, the stated version adds O(n log k) time overhead.
The probability statements also depend on the randomized parts of the construction: perfect hashing, block-boundary detection, chunk checksums and IBLT hashing. The IBLT peeling bound has its own condition, c ≥ 4.
The supplied front matter identifies the work as an arXiv preprint, version 2 dated 27 Aug 2026. It reports an institutional affiliation but no funding statement.
Paper data and sources
Original title: Improved Low-Overhead Communication-Efficient String Reconciliation and Edit Distance
Authors: Michael T. Goodrich, Gonzalo Navarro, Claire A. To
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text