Answers are grounded in this paper and cite their sources.
The number of zeros and the number of ones in a binary string are referred to as the composition of the string, and the prefix-suffix compositions of a string are a multiset formed by the compositions of the prefixes and suffixes of all possible lengths of the string. In this work, we present binary codes of lengthnin which every codeword can be efficiently reconstructed from its erroneous prefix-suffix compositions with at mosttcomposition errors. All our constructions have decoding complexity polynomial innand the best of our constructions has constant rate and can correctt= Θ(n) errors. As a comparison, no prior constructions can afford to efficiently correctt= Θ(n) arbitrary composition errors. Additionally, we propose a method of encodingharbitrary strings of the same length so that they can be reconstructed from the multiset union of their error-free prefix-suffix compositions, at the expense ofh-fold coding overhead. In contrast, existing methods can only recoverhdistinct strings, albeit with code rate asymptotically equal to 1/h. Building on the top of the proposed method, we also present a coding scheme that enables efficient recovery ofhstrings from their erroneous prefix-suffix compositions witht= Θ(n) errors.
No takes yet. Share an insight, caveat, or question.
Zitan Chen (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: