The coded trace reconstruction problem, where multiple noisy copies (traces) of an original message are used for recovery, has garnered significant attention. We investigate this problem under the specific constraints that the messages are permutations of length n and the errors are deletions. Our primary focus is the burst deletion model: given M > 1 traces, each resulting from the original permutation by deleting a single burst of at most t symbols. We present an explicit construction of a permutation code capable of uniquely recovering the original permutation from M = 2 distinct traces, each affected by a burst deletion of size up to t. Notably, this code achieves recovery with only constant redundancy (independent of n). Additionally, we explore a different scenario involving two arbitrary deletions per trace. For this model, we demonstrate that existing 1deletion correcting permutation codes are sufficient to guarantee unique recovery of the original permutation, provided at least M =5 distinct traces are available.

We develop the first parameter-free algorithms for the Stochastically Extended Adversarial (SEA) model, a framework that bridges adversarial and stochastic online convex optimization. Existing approaches for the SEA model require prior knowledge of problem-specific parameters, such as the diameter of the domain $D$ and the Lipschitz constant of the loss functions $G$, which limits their practical applicability. Addressing this, we develop parameter-free methods by leveraging the Optimistic Online Newton Step (OONS) algorithm to eliminate the need for these parameters. We first establish a comparator-adaptive algorithm for the scenario with unknown domain diameter but known Lipschitz constant, achieving an expected regret bound of $\tilde{O}\big(\Vert u\Vert_2^2 + \Vert u\Vert_2(\sqrt{\sigma^2_{1:T}} + \sqrt{\Sigma^2_{1:T}})\big)$, where $u$ is the comparator vector and $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$ represent the cumulative stochastic variance and cumulative adversarial variation, respectively. We then extend this to the more general setting where both $D$ and $G$ are unknown, attaining the comparator- and Lipschitz-adaptive algorithm. Notably, the regret bound exhibits the same dependence on $\sigma^2_{1:T}$ and $\Sigma^2_{1:T}$, demonstrating the efficacy of our proposed methods even when both parameters are unknown in the SEA model.

Localized errors, which occur in windows with bounded lengths, are common in a range of applications. Such errors can be modeled as k-substring edits, which replace one substring with another string, both with lengths upper bounded by k. This generalizes errors such as localized deletions or burst substitutions studied in the literature. In this paper, we show through statistical analysis of real data that substring edits better describe differences between related documents compared to independent edits, and thus commonly arise in problems related to data synchronization. We also show that for the dataset under study, assuming codes exist that can achieve the Gilbert-Varshamov (GV) bound, substring-edit-correcting codes can synchronize two documents with much lower overhead compared to general indel/substitution-correcting codes. Furthermore, given a constant k, we construct binary codes of length n for correcting a single k-substring edit that achieves the GV bound and subsequently has redundancy of asymptotically$2\log n$, compared to$4k\log n$, the lowest redundancy achievable by an existing code for this problem. The time complexities of both encoding and decoding are polynomial with respect to n.

Codes in the Damerau-Levenshtein metric have received some attention by the research community recently owing to their applications in DNA-based data storage. In particular, Gabrys, Yaakobi, and Milenkovic designed a length-n code correcting a single deletion and s adjacent transpositions with at most$(1+2s)\log n$bits of redundancy. In this work, we consider a new setting where both deletions and asymmetric adjacent transpositions may occur. For asymmetric transpositions, at most$s^{+}0$-right shifts (i.e.,$01 \rightarrow 10$) and at most$s^ - 0$-left shifts (i.e.,$10 \rightarrow 01$) may occur. We present several constructions of the binary codes correcting these errors in various cases. In particular, we design a code correcting a single deletion,$s^{+}$right-shift, and$s^ - $left-shift errors with at most$(1+s)\log (n+s+1)+1$bits of redundancy where$s=s^{+}+s^ - $. In addition, we investigate uniquely-decodable codes correcting$t~0$-deletions and s adjacent transpositions with at most$(t+2s)\log n+o(\log n)$bits of redundancy. Then, we study the code for correcting$t~0$-deletions,$s^{+}$right-shift, and$s^ - $left-shift errors with list-decoding algorithms. Our main contribution here is the construction of a list-decodable code with list size$O(n^{s})$and with at most$(\max \{t,s+1\}) \log n+O(1)$bits of redundancy, where$s=s^{+}+s^ - $. We construct non-systematic codes for correcting$t_{\mathrm {b}}$blocks of 0-deletions with$\ell $-limited magnitude and s adjacent transpositions with redundancy at most$(2(t_{\mathrm {b}}+2s)+1)\log (n+1)+O(1)$bits and systematic codes with at most$((2(t_{\mathrm {b}}+2s)+1)(1+1/(\log (t_{\mathrm {b}}\ell +4)))\log (N+1)+O(\log \log N)$redundant bits in an N-length codeword.

Permutation codes in the Ulam metric, which can correct multiple deletions, have been investigated extensively recently. In this work, we are interested in the maximum size of permutation codes in the Ulam metric and aim to design permutation codes that can correct multiple deletions with efficient decoding algorithms. We first present an improvement on the Gilbert–Varshamov bound of the maximum size of these permutation codes by analyzing the independence number of the auxiliary graph. The idea is widely used in various cases and our contribution in this section is to enumerate the number of triangles in the auxiliary graph and show that it is small enough. Next, we design permutation codes correcting multiple deletions with a decoding algorithm. In particular, the constructed permutation codes can correcttdeletions with at most (3t− 1) log(n+ 1) +o(logn) bits of redundancy wherenis the length of the code. Our construction is based on a new mapping that yields a new connection between permutation codes in the Hamming metric and permutation codes in various metrics. Furthermore, we construct permutation codes that correct multiple bursts of deletions using this new mapping. Finally, we extend the new mapping for multi-permutations and construct the best-known multi-permutation codes in the Ulam metric.

Our main goal in this work is to study permutation codes in the Levenshtein metric which can correct multiple deletions. Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall-tau metrics. In this work, we present a new connection between different kinds of distances over two permu-tations' including Hamming, Levenshtein, Ulam, and generalized Kendall-tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permu-tation codes in Levenshtein, Ulam, and generalized Kendall-tau metrics with better size. In particular, we show that there exist permutation codes of length$n$for correcting$t$deletions with at most$(3t+1)\log n+o(\log n)$bits of redundancy. Furthermore, we present the construction of our permutation codes for correcting$t$deletions with a specific decoding process.

Distributed gradient descent has attracted attention in modern machine learning, especially for handling large datasets. Less focus has been given to the distributed gradient descent where the partial gradient in each worker is subject to adversarial corruption instead of random noise. In this paper, we explore the challenges of this adversarial setting and propose a distributed gradient descent algorithm, focusing on the robustness against adversarial corruption and noises during model transmission. Furthermore, we derive bounds on the error rates for both non-strongly convex and strongly convex loss functions.

The problem of correcting deletions has received significant attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a consecutive burst of at most$t$deletions in non-binary sequences. When the alphabet size$q$is even, we first propose a non-binary code correcting a burst of at most 2 deletions for$q$-ary alphabets. Afterwards, we extend this result to the case where the length of the burst can be at most$t$where$t$is a constant. Finally, we consider the setup where the sequences that are transmitted are permutations. The proposed codes are the largest known for their respective parameter regimes.

Localized errors, which occur in windows with bounded lengths, are common in a range of applications. Such errors can be modeled as k-substring edits, which replace one substring with another string, both with lengths upper bounded by k. This generalizes errors such as localized deletions or burst substitutions studied in the literature. In this paper, we show through statistical analysis of real data that substring edits better describe differences between related documents compared to independent edits, and thus commonly arise in problems related to data synchronization. We also show that for the dataset under study, assuming codes exist that can achieve the Gilbert-Varshamov bound, substring-edit-correcting codes can synchronize two documents with much lower overhead compared to general indel/substitution-correcting codes. Furthermore, given a constant k, we construct binary codes of length n for correcting a k-substring edit with redundancy of roughly 2logn, compared to 8logn, the lowest redundancy achievable by an existing code for this problem. The time complexities of both encoding and decoding are polynomial with respect to n.

Codes for correcting sticky insertions/deletions and limited-magnitude errors have attracted significant attention due to their applications of flash memories, racetrack memories, and DNA data storage systems. In this paper, we first consider the error type of t sticky deletions with ℓ-limited-magnitude and propose a non-systematic code for correcting this type of error with redundancy 2t(1 − 1/p) • log(n + 1) + O(1), where p is the smallest prime larger than ℓ + 1. Next, we present a systematic code construction with an efficient encoding and decoding algorithm with redundancy $\frac{{\left\lceil {2t(1 - 1/p)} \right\rceil \cdot \left\lceil {\log p} \right\rceil }}{{\log p}}\log (n + 1) + O(\log \log n)$, where p is the smallest prime larger than ℓ + 1.

Due to its higher data density, longevity, energy efficiency, and ease of generating copies, DNA is considered a promising technology for satisfying future storage needs. However, a diverse set of errors including deletions, insertions, duplications, and substitutions may arise in DNA at different stages of data storage and retrieval. The current paper constructs error-correcting codes for simultaneously correcting short (tandem) duplications and at most$p$edits, where a short duplication generates a copy of a substring with length$\leq 3$and inserts the copy following the original substring, and an edit is a substitution, deletion, or insertion. Compared to the state-of-the-art codes for duplications only, the proposed codes correct up to$p$edits (in addition to duplications) at the additional cost of roughly$8p(\log _{q} n) (1+o(1))$symbols of redundancy, thus achieving the same asymptotic rate, where$q\ge 4$is the alphabet size and$p$is a constant. Furthermore, the time complexities of both the encoding and decoding processes are polynomial when$p$is a constant with respect to the code length.

Due to its higher data density, longevity, energy efficiency, and ease of generating copies, DNA is considered a promising storage technology for satisfying future needs. However, a diverse set of errors including deletions, insertions, duplications, and substitutions may arise in DNA at different stages of data storage and retrieval. The current paper constructs error-correcting codes for simultaneously correcting short (tandem) duplications and at most p substitutions, where a short duplication generates a copy of a substring with length ≤3 and inserts the copy following the original substring. Compared to the state-of-the-art codes for duplications only, the proposed codes correct up to p substitutions (in addition to duplications) at the additional cost of roughly 8p(logqn)(1 + o(1)) symbols of redundancy, thus achieving the same asymptotic rate, where q ≥ 4 is the alphabet size. Furthermore, the time complexities of both the encoding and decoding processes are polynomial when p is a constant with respect to n.

Codes in the Damerau–Levenshtein metric have been studied recently owing to their applications in DNA-based data storage. In previous work, codes for correcting a single deletion and multiple adjacent transpositions were presented. In this work, we consider a new setting with the asymmetric Damerau–Levenshtein distance where both 0-deletions and adjacent transpositions occur. We first study uniquely-decodable codes and present an optimal code (in the sense that its redundancy is optimal up to a constant additive term) correcting a single 0-deletion or a single adjacent transposition with redundancy log n + 2 bits. Then, we present a construction of codes correcting t 0-deletions and s adjacent transpositions with at most (t + 2s) log n bits of redundancy. Next, we focus on list-decodable codes and construct a list-decodable code with list-size O(nmin{s+1,t}) and has at most (max{t, s + 1}) log n bits of redundancy.

The problem of correcting deletions has recently received significantly increased attention, partly because of the prevalence of these errors in DNA data storage. In this paper, we study the problem of correcting a burst of at most two deletions in non-binary sequences. The problem was first studied for binary sequences by Levenshtein, who presented a construction with optimal redundancy. We propose a non-binary code correcting a burst of at most 2 deletions for q-ary alphabets with redundancy$\log n+O$(log$q$log log n) bits, for even$q$. Further, we construct codes with lower redundancy to correct a burst of exactly 2 deletions caused by a single deletion in alternating sequences that arise in terminator-free enzymatic DNA synthesis.

In this article, we investigate a two-hop decode-and-forward (DF) multicasting multiple-input multiple-output (MIMO) wireless relay communication system. Different to conventional systems, the radio frequency (RF) energy from the source node is harvested at the relay node and used for forwarding signals to a group of receivers. Considering the structure of the energy harvesting (EH) relay node, we present a power splitting (PS) based protocol and a novel time switching (TS) based protocol by introducing two additional TS factors. For both protocols, we maximize the system mutual information (MI) of the multicasting MIMO relay system by jointly optimizing the source and relay covariance matrices under the constraints of the source energy and the relay harvested energy. In addition, a practical nonlinear EH model is adopted, where the energy harvested by the relay node is bounded as the incident RF signal power increases, and the harvested power is zero when the input power is below the minimum power for harvesting. For the TS based protocol, we also consider peak transmission power constraints at both the source and relay nodes. The performance of the proposed algorithms is verified via numerical simulations. The results demonstrate that the novel TS based protocol achieves a larger MI than the conventional TS protocol. The PS and TS based protocols achieve tradeoffs at different source power levels. In particular, compared with the PS based protocol, the proposed novel TS based protocol can reach a higher system MI when the EH bound is not reached, while the former protocol reaches a higher MI when the EH circuit is saturated. We show that the peak harvested energy constraint plays an important role in selecting the optimal location of the relay node.

Impulsive noise can greatly affect the performance of underwater acoustic (UA) orthogonal frequency-division multiplexing (OFDM) systems. In this paper, by utilizing the sparsity of the UA channel impulse response and impulsive noise, we first propose a novel sparse Bayesian learning (SBL) based expectation maximization (EM) algorithm for joint channel estimation and impulsive noise mitigation in UA OFDM systems. Secondly, considering that the UA channel and impulsive noise are fast time-varying, we develop a new approach which combines the SBL with the forward-backward Kalman filtering to track the UA channel and impulsive noise. To further improve the system performance, we utilize the information available on data subcarriers for joint time-varying channel estimation and data detection, based on the SBL algorithm and the Kalman filter. The performance of our proposed algorithms is verified through both numerical simulations and by data collected during a UA communication experiment conducted in the estuary of the Swan River, Perth, Australia. The results demonstrate that compared with existing approaches, the proposed algorithms achieve a better system bit-error-rate and frame-error-rate performance.