Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem that lies within the foundation of a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present three perspectives on this problem: a graph theoretic framework due to Pevzner, an automata theoretic approach from our previous work, and a new insight that yields a time-optimal streaming algorithm for determining whether a string of @math characters over the alphabet @math can be uniquely decoded from its two-character shingles. Our algorithm achieves an overall time complexity @math and space complexity @math . As an application, we demonstrate how this algorithm can be extended to larger shingles for efficient string reconciliation.
The problem of set reconciliation seeks to reconcile two remote sets @math and @math of @math -bit integers using minimum communication. The approach in @cite_0 involves translating the set elements into an equivalent , so that the problem of set reconciliation is reduced to an equivalent problem of rational function interpolation, much like in Reed-Solomon decoding @cite_15 .
@cite_0 @cite_15
2142423295 1606480398
We consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. This type of problem arises naturally from gossip protocols used for the distribution of information, but has other applications as well. We describe an approach to such reconciliation based on the encoding of sets as polynomials. The resulting protocols exhibit tractable computational complexity and nearly optimal communication complexity. Moreover, these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a single broadcast. Linear Codes. Nonlinear Codes, Hadamard Matrices, Designs and the Golay Code. An Introduction to BCH Codes and Finite Fields. Finite Fields. Dual Codes and Their Weight Distribution. Codes, Designs and Perfect Codes. Cyclic Codes. Cyclic Codes: Idempotents and Mattson-Solomon Polynomials. BCH Codes. Reed-Solomon and Justesen Codes. MDS Codes. Alternant, Goppa and Other Generalized BCH Codes. Reed-Muller Codes. First-Order Reed-Muller Codes. Second-Order Reed-Muller, Kerdock and Preparata Codes. Quadratic-Residue Codes. Bounds on the Size of a Code. Methods for Combining Codes. Self-dual Codes and Invariant Theory. The Golay Codes. Association Schemes. Appendix A. Tables of the Best Codes Known. Appendix B. Finite Geometries. Bibliography. Index.