Reconstruction Codes for Deletions and Insertions: Connection, Distinction, and Construction

LetB(·) be an error ball function. A set ofq-ary sequences of lengthnis referred to as an (n, q, N; B)-reconstruction codeif each sequencexwithin this set can be uniquely reconstructed from anyNdistinct elements within its error ballB(x). The main objective in this area is to determine or establish bounds for the minimum redundancy of (n, q, N; B)-reconstruction codes, denoted by ρ(n, q, N; B). In this paper, we investigate reconstruction codes where the error ball corresponds to either thet-deletion ball Dt(·) or thet-insertion ball It(·). Our primary technical contributions include: • Establishing a fundamental connection between reconstruction codes for deletions and insertions. Specifically, for any positive integersn, t, q, N, any (n, q, N; It)-reconstruction code is also an (n, q, N; Dt)-reconstruction code. This leads to the inequality ρ(n, q, N; Dt) ≤ ρ(n, q, N; It). • Identifying a significant distinction between reconstruction codes for deletions and insertions whenN=O(nt−1) andt≥ 2. For deletions, we prove that there exists some constantKsuch that ρ(n, q,2(q−1)t−1/qt−1(t−1)!nt−1+Knt−2;Dt) =O(1), which disproves a conjecture posed in [1]. In contrast, for insertions, we show that there exists some constantK′ such that ρ(n, q,(q−1)t−1(t−1)!nt−1+K′nt−2;It) = log logn+O(1), which extends a key result from [2]. • Constructing (n, q, N; B)-reconstruction codes, whereB∈ {D2,I2}, forN∈ {2, 3, 4, 5} and establishing respective upper bounds of 3 logn+O(log logn), 3 logn+O(1), 2 logn+ O(log logn) and logn+ O(log logn) on the minimum redundancy ρ(n, q, N; B). This generalizes results previously established in [3].