Search

A central question in the era of big data is what to do with the enormous amount of information. One possibility is to characterize it through statistics, e.g., averages, or classify it using machine learning, in order to understand the general structure of the overall data. The perspective in this paper is the opposite, namely that most of the value in the information in some applications is in the parts that deviate from the average, that are unusual, atypical. We define what we mean by atypical in an axiomatic way as data that can be encoded with fewer bits in itself rather than using the code for the typical data. We show that this definition has good theoretical properties. We then develop an implementation based on universal source coding, and apply this to a number of real world data sets. [ABSTRACT FROM AUTHOR]

We consider the probabilistic group testing problem where $d$ random defective items in a large population of $N$ items are identified with high probability by applying binary tests. It is known that the $\Theta (d \log N)$ tests are necessary and sufficient to recover the defective set with vanishing probability of error when $d = O(N^{\alpha })$ for some $\alpha \in (0, 1)$. However, to the best of our knowledge, there is no explicit (deterministic) construction achieving $\Theta (d \log N)$ tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of $d$) achieves the order optimal $\Theta (d \log N)$ tests in the probabilistic group testing problem when $d = \Omega (\log ^{2}\,\,N)$. This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of $d$. To prove the order-optimality of Kautz and Singleton’s construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests. [ABSTRACT FROM AUTHOR]

In this paper, we study the decoding of dual-containing codes from Hermitian tower and applications to quantum codes. The contribution of this paper is threefold. First, we construct the quantum stabilizer codes from the Hermitian tower. Second, we provide a deterministic decoding algorithm with decoding radius that almost achieves the optimal decoding radius, i.e., $(1-R)/4$ , where $R$ is the rate. Last and most importantly, we present a Monte Carlo algorithm with decoding radius roughly equal to $(1-R)/3$ , which is beyond the optimal decoding radius $(1-R)/4$ . There are several features in this paper. First of all, we employ a differential for the Hermitian tower. This differential plays a crucial role for decoding. We also extend our decoding by passing to the constant field extension. This constant field extension makes the decoding work perfectly. [ABSTRACT FROM PUBLISHER]

Because of their efficient encoding and decoding algorithms, cyclic codes—an interesting class of linear codes—are widely used in communication systems, storage devices, and consumer electronics. BCH codes form a special class of cyclic codes, and are usually among the best cyclic codes. A subclass of good BCH codes is the narrow-sense primitive BCH codes. However, the dimension and minimum distance of these codes are not known in general. The main objective of this paper is to study the dimension and minimum distances of a subclass of the narrow-sense primitive BCH codes with design distance \delta =(q-\ell 0)q^{m-\ell 1-1}-1 for certain pairs (\ell 0, \ell 1) , where 0 \leq \ell 0 \leq q-2 and 0 \leq \ell 1 \leq m-1 . The parameters of other related classes of BCH codes are also investigated, and some open problems are proposed in this paper. [ABSTRACT FROM PUBLISHER]

We consider the problem of multiple descriptions (MDs) source coding and propose new coding strategies involving both unstructured and structured coding layers. Previously, the most general achievable rate-distortion (RD) region for the $l$ -descriptions problem was the combinatorial message sharing with binning (CMSB) region. The CMSB scheme utilizes unstructured quantizers and unstructured binning. In the first part of the paper, we show that this strategy can be improved upon using more general unstructured quantizers and a more general unstructured binning method. In the second part, structured coding strategies are considered. First, structured coding strategies are developed by considering the specific MD examples involving three or more descriptions. We show that the application of structured quantizers results in strict RD improvements when there are more than two descriptions. Furthermore, we show that a structured binning also yields improvements. These improvements are in addition to the ones derived in the first part of the paper. This suggests that structured coding is essential when coding over more than two descriptions. Using the ideas developed through these examples, we provide a new unified coding strategy by considering several structured coding layers. Finally, we characterize its performance in the form of an inner bound to the optimal RD region using computable single-letter information quantities. The new RD region strictly contains all of the previous known achievable regions. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density parity-check (LDPC) codes. These sets are known to be the main culprits in the error floor region of such codes. The characterization of ETSs for irregular codes has been known to be a challenging problem due to the large variety of non-isomorphic ETS structures that can exist within the Tanner graph of these codes. This is a direct consequence of the variety of the degrees of the variable nodes that can participate in such structures. The proposed characterization is based on a hierarchical graphical representation of ETSs, starting from simple cycles of the graph, or from single variable nodes, and involves three simple expansion techniques: degree-one tree ( dot ), path , and lollipop , thus, the terminology dpl characterization. A similar dpl characterization was proposed in an earlier work by the authors for the leafless ETSs of variable–regular LDPC codes. The present paper generalizes the prior work to codes with a variety of variable node degrees and to ETSs that are not leafless. The proposed dpl characterization corresponds to an efficient search algorithm that, for a given irregular LDPC code, can find all the instances of (a, b) ETSs with size a and b \leq b\max , exhaustively. Although branch-&-bound exhaustive search algorithms for finding ETSs of irregular LDPC codes exist, to the best of our knowledge, the proposed search algorithm is the first of its kind, in that, it is devised based on a characterization of ETSs that makes the search process efficient. For a constant degree distribution and range of search, the worst-case complexity of the proposed dpl algorithm increases linearly with the block length $n$ . The average complexity, excluding the search for the input simple cycles, is constant in $n$ . Extensive simulation results are presented to show the versatility of the search algorithm, and to demonstrate that, compared to the literature, significant improvement in search speed can be obtained. [ABSTRACT FROM PUBLISHER]

We analyze the asymptotics of the normalized remaining uncertainty of a source when a compressed or hashed version of it and correlated side information is observed. For this system, commonly known as Slepian–Wolf source coding, we establish the optimal (minimum) rate of compression of the source to ensure that the remaining uncertainties vanish. We also study the exponential rate of decay of the remaining uncertainty to zero when the rate is above the optimal rate of compression. In this paper, we consider various classes of random universal hash functions. Instead of measuring remaining uncertainties using traditional Shannon information measures, we do so using two forms of the conditional Rényi entropy. Among other techniques, we employ new one-shot bounds and the moments of type class enumerator method (see Merhav) for these evaluations. We show that these asymptotic results are generalizations of the strong converse exponent and the error exponent of the Slepian–Wolf problem under maximum a posteriori decoding. [ABSTRACT FROM PUBLISHER]

It is a well-known fact that the Discrete Fourier Transform (DFT) \vec X of an arbitrary n -length input signal \vec {x} , can be computed from all the n time-domain samples in O( n\log n) operations via a Fast Fourier Transform (FFT) algorithm. If the spectrum k -sparse (where k\ll n ), can we do better? We show that asymptotically in k and n , when k ), where 0 \leq \delta <1 ), and the support of the non-zero DFT coefficients is uniformly random, the fast fourier aliasing-based sparse transform (FFAST) algorithm, proposed in this paper, computes, with asymptotically high probability, the k non-zero DFT coefficients of from O( k) samples of \vec x in O( k\log k) arithmetic operations. Further, the constants in the big Oh notation for both sample and computational cost are small, e.g., when \delta < 0.99 , which essentially covers a wide range of sub-linear sparsity cases, the sample cost is less than 4 k . Although, in this paper we assume that the samples of the signal \vec x observed by the FFAST are noise-free, a noise-robust extension of the FFAST is provided in a companion (Part II) paper [1]. Our approach is based on filter-less sub-sampling of the input signal using a set of carefully chosen uniform sub-sampling patterns guided by the Chinese Remainder Theorem (CRT). The idea is to cleverly exploit, rather than avoid, the resulting aliasing artifacts induced by sub-sampling. Specifically, the sub-sampling operation on the time-domain signal \vec x is designed to create aliasing patterns of the non-zero coefficients of the spectrum \vec X to “look like” parity-check constraints of a good erasure-correcting sparse-graph code. Next, we show that computing the sparse DFT \vec X is equivalent to decoding of an appropriate sparse-graph code. The sparse-graph codes further permit a fast peeling-style decoding. Consequently, the resulting DFT computation is low in both the sample and the decoding complexity. We analytically connect our proposed CRT-based aliasing framework to random sparse-graph codes, and analyze the performance of our algorithm using density evolution techniques from coding theory. We provide extensive simulation results, that are in tight agreement with our theoretical findings. [ABSTRACT FROM PUBLISHER]

Current approaches to the practical implementation of network coding are batch-based, and often do not use feedback, except possibly to signal completion of a file download. In this paper, the various benefits of using feedback in a network coded system are studied. It is shown that network coding can be performed in a completely online manner, without the need for batches or generations, and that such online operation does not affect the throughput. Although these ideas are presented in a single-hop packet erasure broadcast setting, they naturally extend to more general lossy networks, which employ network coding in the presence of feedback. The impact of feedback on sender-side queue size and receiver-side decoding delay is studied in an asymptotic sense as the traffic load approaches capacity. Different notions of decoding delay are considered, including an order-sensitive notion, which assumes that packets are useful only when delivered in order. Strategies for adaptive coding based on feedback are presented. Our scheme achieves throughput optimality and asymptotically optimal sender queue size and is conjectured to achieve asymptotically optimal in-order delivery delay for any number of receivers. This paper may be viewed as a natural extension of Automatic Repeat reQuest to coded networks. [ABSTRACT FROM PUBLISHER]

Communication over a random-parameter quantum channel when the decoder is required to reconstruct the parameter sequence is considered. We study scenarios that include either strictly-causal, causal, or non-causal channel side information (CSI) available at the encoder, and also when CSI is not available. This model can be viewed as a form of quantum metrology, and as the quantum counterpart of the classical rate-and-state channel with state estimation at the decoder. Regularized formulas for the capacity-distortion regions are derived. In the special case of measurement channels, single-letter characterizations are derived for the strictly-causal and causal settings. Furthermore, in the more general case of entanglement-breaking channels, a single-letter characterization is derived when CSI is not available. As a consequence, we obtain regularized formulas for the capacity of random-parameter quantum channels with CSI, generalizing previous results by Boche et al., 2016, on classical-quantum channels. Bosonic dirty paper coding is introduced as a consequence, where we demonstrate that the optimal coefficient is not necessarily that of minimum mean-square error estimation as in the classical setting. [ABSTRACT FROM AUTHOR]

In this paper, we formulate the problem to cope with the transmission of extra bits over an existing coded transmission link (referred to as coded payload link) without any cost of extra transmission energy or extra bandwidth. This is possible since a gap to the channel capacity typically exists for a practical code. A new concept, termed as accessible capacity, is introduced to specify the maximum rate at which the superposition transmission of extra bits is reliable and has a negligible effect on the performance of the coded payload link. For a binary-input output-symmetric (BIOS) memoryless channel, the accessible capacity can be characterized as the difference between the channel capacity and the mutual information rate of the coded payload link, which can be numerically evaluated for very short payload codes. For a general payload code, we present a simple lower bound on the accessible capacity, given by the channel capacity minus the coding rate of the payload code. We then focus on the scenarios where low-density parity-check (LDPC) codes are implemented for the payload link. We propose to transmit extra bits by random superposition for encoding, and exhaustive search (with the aid of statistical learning) for decoding. We further propose, by establishing an auxiliary channel (called syndrome channel) induced from “zero-forcing” over the binary field, to transmit extra bits with structured codes such as repetition codes and first-order Reed-Muller (RM) codes. Numerical results show that up to 60 extra bits can be reliably transmitted along with a rate-1/2 LDPC code of length 8064. [ABSTRACT FROM AUTHOR]

Distributed Arithmetic Coding (DAC) is a practical realization of Slepian-Wolf coding that partitions source space into cosets. Coset Cardinality Spectrum (CCS) is an important property of DAC that was defined in our previous work. In this paper, we give two applications of CCS. First, we find that DAC bitstream is not compact. The rate loss of DAC bitstream is caused by two factors: unequal coset partitioning and bit indivisibility. It is proved that as code length goes to infinity, the expected value of bit-indivisibility rate loss will tend to 0.5 for any irrational Rate Change Step (RCS), where the RCS refers to the rate change when one source bit is flipped. With the help of CCS, the bit-indivisibility rate loss can be compensated to some extend. Especially, for any irrational RCS, as code length goes to infinity, the expected value of the remaining bit-indivisibility rate loss after compensation will tend to about 0.47. The second application of CCS is DAC decoder design. We derive the formula of path metric and find that in the original paper on DAC, the intuitive formula of path metric is not correct. The backward-replacing algorithm is proposed to make full use of memory. Experimental results confirm the correctness of theoretical analyses. [ABSTRACT FROM AUTHOR]

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

A multi-resolution quantizer is a sequence of quantizers where the output of a coarser quantizer can be deduced from the output of a finer quantizer. In this paper, we propose an asymptotically scale-invariant multi-resolution quantizer, which performs uniformly across any choice of average quantization step, when the length of the range of input numbers is large. Scale invariance is especially useful in worst case or adversarial settings, ensuring that the performance of the quantizer would not be affected greatly by small changes of storage or error requirements. We also show that the proposed quantizer achieves a tradeoff between rate and error that is arbitrarily close to the optimum. [ABSTRACT FROM AUTHOR]

Deletion errors are notoriously difficult to correct. The capacity of the binary deletion channel is not yet fully known, and there is no completely satisfactory solution even to the specific problem of correcting only two deletion errors. In this paper, we show that polarization theory, along with the powerful methods of polar coding and successive-cancellation decoding, can be extended to channels with deletion errors. Our results further generalize to channels corrupted by insertion errors and/or combinations of insertions and deletions. It was recently proposed to correct deletion errors using polar codes designed for the BEC, precoded with a sufficiently powerful CRC code. In this approach, in order to correct ${d}$ deletions in a codeword of length ${n}$ , successive-cancellation decoding is run separately for each of the $\binom {n}{d}$ possible deletion patterns, while treating the deleted symbols as erasures. The resulting complexity of decoding is ${O}\bigl ({n}^{d+1}\log {n}\bigr)$. In contrast, we develop herein a natural generalization of successive-cancellation decoding to channels with deletion errors. Our algorithm is based on the recursive structure of polar codes, processing the channel output in ${m} = \log _{2} {n}$ decoding layers, just like the conventional successive-cancellation decoder. Every node in each decoding layer propagates its uncertainty about the deletion pattern to the nodes in the next layer and, eventually, the correct deletion pattern becomes visible at the decoder output, with high probability. This makes it possible to consider at most $\binom {d+2}{2}$ scenarios at each node, and the overall decoding complexity is only ${O}\bigl ({d}^{3} {n} \log {n}\bigr)$ , which scales polynomially rather than exponentially with the number of deletions. Based on the proposed algorithm, we also investigate the channel polarization phenomenon. We are able to prove weak polarization where the number of deletions ${d}$ is small, i.e. ${d}={o}({n})$. We also conjecture the strong polarization for when ${d}={O}(1)$ and provide some evidence to support this conjecture. The strong polarization, if proven, implies that our coding scheme achieves the capacity of any binary-input symmetric channel which furthermore introduces a constant number of deletions. [ABSTRACT FROM AUTHOR]

Existing fixed-length feedback communication schemes are either specialized to particular channels (Schalkwijk–Kailath, Horstein), or apply to general channels but either have high coding complexity (block feedback schemes) or are difficult to analyze (posterior matching). This paper introduces a new fixed-length feedback coding scheme which achieves the capacity for all discrete memoryless channels, has an error exponent that approaches the sphere packing bound as the rate approaches the capacity, and has $O(n\log n)$ coding complexity. These benefits are achieved by judiciously combining features from previous schemes with new randomization technique and encoding/decoding rule. These new features make the analysis of the error probability for the new scheme easier than for posterior matching. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of channel simulation via interactive communication, known as the coordination capacity, in a two-terminal network. We assume that two terminals observe independent identically distributed (i.i.d.) copies of two random variables and would like to generate i.i.d. copies of two other random variables jointly distributed with the observed random variables. The terminals are provided with two-way communication links, and shared common randomness, all at limited rates. Two special cases of this problem are the interactive function computation studied by Ma and Ishwar, and the tradeoff curve between one-way communication and shared randomness studied by Cuff. The latter work had inspired Gohari and Anantharam to study the general problem of channel simulation via interactive communication stated above. However, only inner and outer bounds for the special case of no shared randomness were obtained in their work. In this paper, we settle this problem by providing an exact computable characterization of the multiround problem. To show this we employ the technique of output statistics of random binning that has been recently developed by the authors. [ABSTRACT FROM AUTHOR]

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2. [ABSTRACT FROM AUTHOR]

This paper considers the problem of variable-length coding over a discrete memoryless channel with noiseless feedback. This paper provides a stochastic control view of the problem whose solution is analyzed via a newly proposed symmetrized divergence, termed extrinsic Jensen–Shannon (EJS) divergence. It is shown that strictly positive lower bounds on EJS divergence provide nonasymptotic upper bounds on the expected code length. This paper presents strictly positive lower bounds on EJS divergence, and hence nonasymptotic upper bounds on the expected code length, for the following two coding schemes: 1) variable-length posterior matching and 2) MaxEJS coding scheme that is based on a greedy maximization of the EJS divergence. As an asymptotic corollary of the main results, this paper also provides a rate–reliability test. Variable-length coding schemes that satisfy the condition(s) of the test for parameters $R$ and $E$ are guaranteed to achieve a rate $R$ and an error exponent $E$ . The results are specialized for posterior matching and MaxEJS to obtain deterministic one-phase coding schemes achieving capacity and optimal error exponent. For the special case of symmetric binary-input channels, simpler deterministic schemes of optimal performance are proposed and analyzed. [ABSTRACT FROM AUTHOR]

In this paper, we prove the separation of source-network coding and channel coding in wireline networks. For the purposes of this paper, a wireline network is any network of independent, memoryless, point-to-point, and finite-alphabet channels used to transmit dependent sources either losslessly or subject to a distortion constraint. In deriving this result, we also prove that in a general memoryless network with dependent sources, lossless, and zero-distortion reconstruction are equivalent provided that the conditional entropy of each source given the other sources is nonzero. Furthermore, we extend the separation result to the case of continuous-alphabet and point-to-point channels, such as additive white Gaussian noise channels. [ABSTRACT FROM AUTHOR]

Motivated by applications in molecular biology and genotyping, this paper proposes a novel model of group testing for identifying items with real-valued status using nonbinary pooling designs under standard arithmetic observation. The purpose is to learn more information of each item to be tested rather than identify only which ones are defectives as was done in conventional group testing. This paper provides several efficiently decodable nonadaptive strategies for the considered problem. The major tool is a new structure called $q$ -ary additive $(w,d)$ -disjunct matrix, which is related to known structures: 1) the conventional disjunct matrix by Kautz and Singleton 1964 and 2) the SQ-disjunct matrix by Emad and Milenkovic 2012. [ABSTRACT FROM AUTHOR]

In this paper, the basic function field of an asymptotically optimal tower of function fields by Garcia and Stichtenoth is studied, where bases of one-point linear systems can be explicitly constructed. A representation of finite GF(q^2) -rational points on the associated plane curve is derived in this paper. This representation is exploited to extend the use of Horner’s loops and the mechanism of Chien search in the decoding of Reed–Solomon codes for syndrome generation and error-location search, respectively, to algebraic-geometry codes built on the plane Garcia–Stichtenoth curve. [ABSTRACT FROM AUTHOR]

The most computationally intensive step of the Guruswami–Sudan list decoder for generalized Reed–Solomon codes is the formation of a bivariate interpolation polynomial. Complexity can be reduced if this polynomial has prefactors, i.e., factors of its univariate constituent polynomials that are independent of the received vector, and hence known a priori. For example, the well-known re-encoding projection due to Koetter et al. leads to one class of prefactors. This paper introduces so-called Sierpínski prefactors that result from the property that many binomial coefficients, which arise in the multiplicity constraints defined in terms of the Hasse derivative, are zero modulo the underlying field characteristic. It is shown that re-encoding prefactors and Sierpínski prefactors can be combined to achieve a significantly reduced Guruswami–Sudan interpolation step. In certain practically relevant cases, the introduction of Sierpínski prefactors reduces the number of unknown polynomial coefficients by an additional 10% or more (beyond the reduction due to re-encoding prefactors alone), without incurring additional computational effort at the decoder. [ABSTRACT FROM AUTHOR]

This paper provides a unified framework to study the performance of successive interference cancellation (SIC) in wireless networks with arbitrary fading distribution and power-law path loss. An analytical characterization of the performance of SIC is given as a function of different system parameters. The results suggest that the marginal benefit of enabling the receiver to successively decode \(k\) users diminishes very fast with \(k\) , especially in networks of high dimensions and small path loss exponent. On the other hand, SIC is highly beneficial when the users are clustered around the receiver and/or very low-rate codes are used. In addition, with multiple packet reception, a lower per-user information rate always results in higher aggregate throughput in interference-limited networks. In contrast, there exists a positive optimal per-user rate that maximizes the aggregate throughput in noisy networks. The analytical results serve as useful tools to understand the potential gain of SIC in heterogeneous cellular networks (HCNs). Using these tools, this paper quantifies the gain of SIC on the coverage probability in HCNs with nonaccessible base stations. An interesting observation is that, for contemporary wireless systems (e.g., LTE and WiFi), most of the gain of SIC is achieved by canceling a single interferer. [ABSTRACT FROM AUTHOR]

This paper considers the problem of minimum cost communication of correlated sources over a network with multiple sinks, which consists of distributed source coding followed by routing. We introduce a new routing paradigm called dispersive information routing (DIR), wherein the intermediate nodes are allowed to split a packet and forward subsets of the received bits on each of the forward paths. This paradigm opens up a rich class of research problems, which focus on the interplay between encoding and routing in a network. Unlike conventional routing methods such as in [1], DIR ensures that each sink receives just the information needed to reconstruct the sources it is required to reproduce. We demonstrate using simple examples that the proposed approach offers better asymptotic performance than conventional routing techniques. We show that, under certain assumptions on the cost function, the problem of finding the minimum cost under DIR essentially reduces to characterizing an achievable rate region for a new multiterminal information theoretic setup. While it is possible to derive an achievable region for this setup using prior results from general multiterminal source coding [3], these techniques do not exploit the underlying problem structure and thereby lead to suboptimal regions. In this paper, we propose a new coding scheme, using principles from multiple descriptions encoding [2], and show that it strictly improves upon a corresponding variant of coding scheme in [3]. We further show that the new coding scheme achieves the complete rate region for certain special cases of the general setup and thereby achieves the minimum communication cost under this routing paradigm. [ABSTRACT FROM PUBLISHER]

In this paper, we study linear encoding for a pair of correlated Gaussian sources transmitted over a two-user Gaussian broadcast channel in the presence of unit-delay noiseless feedback, abbreviated as the GBCF. Each pair of source samples is transmitted using a linear transmission scheme in a finite number of channel uses. We investigate three linear transmission schemes: A scheme based on the Ozarow–Leung (OL) code, a scheme based on the linear quadratic Gaussian (LQG) code of Ardestanizadeh et al., and a novel scheme derived in this paper using a dynamic programming (DP) approach. For the OL and LQG schemes we present lower and upper bounds on the minimal number of channel uses needed to achieve a target mean-square error (MSE) pair. For the LQG scheme in the symmetric setting, we identify the optimal scaling of the sources, which results in a significant improvement of its finite horizon performance, and, in addition, characterize the (exact) minimal number of channel uses required to achieve a target MSE. Finally, for the symmetric setting, we show that for any fixed and finite number of channel uses, the DP scheme achieves an MSE lower than the MSE achieved by either the LQG or the OL schemes. [ABSTRACT FROM AUTHOR]

Consider a binary Reed–Muller code RM (r,m) defined on the m -dimensional hypercube \mathbb F2^{m} . In this paper, we study punctured Reed–Muller codes Pr(m,b) , whose positions are restricted to the m -tuples of a given Hamming weight b . In combinatorial terms, this paper concerns m -variate Boolean polynomials of any degree r , which are evaluated on a Hamming sphere of some radius b . Codes Pr(m,b) inherit some recursive properties of RM codes. In particular, they can be built from the shorter codes, by decomposing a spherical b -layer into sub-layers of smaller dimensions. However, these sub-layers have different sizes and do not form the classical Plotkin construction. We analyze recursive properties of the spherically punctured codes Pr(m,b) and find their distances for the arbitrary values of parameters $r,m$ , and $b$ . Finally, we describe recursive (successive cancellation) decoding of these codes. [ABSTRACT FROM AUTHOR]

This paper studies the problem of the distributed compression of correlated sources with an action-dependent joint distribution. This class of problems is, in fact, an extension of the Slepian–Wolf model, but where cost-constrained actions taken by the encoder or the decoder affect the generation of one of the sources. The purpose of this paper is to study the impact of actions on the achievable rates. In particular, two cases where transmission occurs over a rate-limited link are studied; case A for actions taken at the decoder and case B where actions are taken at the encoder. A complete single-letter characterization of the set of achievable rates is given in both cases. Furthermore, a network coding setup for the case where actions are taken at the encoder is investigated. The sources are generated at different nodes of the network and are required at a set of terminal nodes, yet transmission occurs over a general, acyclic, directed network. For this setup, generalized cut-set bounds are derived, and a full characterization of the set of achievable rates using single-letter expressions is provided. For this scenario, random linear network coding is proved to be optimal, even though this is not a classical multicast problem. In addition, two binary examples are investigated and demonstrate how actions taken at different nodes of the system have a significant effect on the achievable rate region, when compared with a naive time-sharing strategy. [ABSTRACT FROM AUTHOR]

Efficient list decoding of rank-metric codes seems more difficult compared with classical block codes although list decodability of random rank-metric codes is completely determined by Ding. For example, it was shown by Raviv and Wachter-Zeh that the list decoding radius of Gabidulin codes is the same as the unique decoding radius, i.e., half the minimum distance for some instances of parameters. On the other hand, Guruswami and Xing give an explicit construction of subcodes of Gabidulin codes, which can be list decoded up to the Singleton bound. This implies that subcodes of Gabidulin codes are good candidates for list decoding. In this paper, we confirm that, with overwhelming probability, a random subcode of a Gabidulin code can be list decoded with decoding radius far beyond half of the minimum distance. [ABSTRACT FROM PUBLISHER]

This paper considers network communications under a hard timeliness constraint, where a source node streams perishable information to a destination node over a directed acyclic graph subject to a hard delay constraint. Transmission along any edge incurs unit delay, and it is required that every information bit generated at the source at the beginning of time t to be received and recovered by the destination at the end of time t+ {\mathrm {D}}-1 , where {\mathrm {D}}>0$ is the maximum allowed end-to-end delay. We study the corresponding delay-constrained unicast capacity problem. This paper presents the first example showing that network coding (NC) can achieve strictly higher delay-constrained throughput than routing even for the single unicast setting and the NC gain can be arbitrarily close to 2 in some instances. This is in sharp contrast to the delay-unconstrained ( {\mathrm {D}}=\infty ) single-unicast case where the classic min-cut/max-flow theorem implies that coding cannot improve throughput over routing. Motivated by the above findings, a series of investigation on the delay-constrained capacity problem is also made, including: 1) an equivalent multiple-unicast representation based on a time-expanded graph approach; 2) a new delay-constrained capacity upper bound and its connections to the existing routing-based results [Ying et al. 2011]; 3) an example showing that the penalty of using random linear NC can be unbounded; and 4) a counter example of the tree-packing Edmonds’ theorem in the new delay-constrained setting. Built upon the time-expanded graph approach, we also discuss how our results can be readily extended to cyclic networks. Overall, our results suggest that delay-constrained communication is fundamentally different from the well-understood delay-unconstrained one and call for investigation participation. [ABSTRACT FROM PUBLISHER]

Fire codes are cyclic codes generated by the product of two polynomials: a binomial that characterizes the code’s guaranteed burst-correcting capability and an irreducible polynomial that characterizes the code length. However, the true burst-correcting capability of a Fire code may exceed its guaranteed burst-correcting capability, which can be thought of as the designed burst-correcting capability of the Fire code. The true burst-correcting capability of a Fire code depends on the irreducible polynomial used in code construction. In this paper, the maximum true burst-correcting capabilities of Fire codes are considered. Fire codes are classified based on three parameters: their designed burst-correcting capabilities, the least common multiple of the periods of the binomials, and the irreducible polynomials used in their constructions, and the ratios of the periods of primitive polynomials of the same degrees as the irreducible polynomials to the periods of the irreducible polynomials. It is shown that the maximum true burst-correcting capability of each class, which pertains to an infinite number of codes, can be determined by checking whether or not a finite number of incongruences have a solution. It is also shown that in each class, there is an infinite number of Fire codes, with increasing code lengths, that attain this maximum. The maximum true burst-correcting capabilities of several classes of Fire codes are determined. It is also shown that there are infinite sequences of irreducible polynomials that generate cyclic codes of rates approaching one and with burst-correcting capabilities that exceed any given number. [ABSTRACT FROM AUTHOR]

Maximum-distance separable (MDS) convolutional codes form an optimal family of convolutional codes, the study of which is of great importance. There are very few general algebraic constructions of MDS convolutional codes. In this paper, we construct a large family of partial-unit-memory MDS convolutional codes over \mathbb Fq with flexible parameters. Compared with the previous work, the field size $q$ required to define these codes is much smaller. The construction also leads to many new strongly MDS convolutional codes, an important subclass of MDS convolutional codes. Some examples are presented at the end of this paper. [ABSTRACT FROM AUTHOR]

This paper studies a generalization of sparse superposition codes (SPARCs) for communication over the complex additive white Gaussian noise (AWGN) channel. In a SPARC, the codebook is defined in terms of a design matrix, and each codeword is a generated by multiplying the design matrix with a sparse message vector. In the standard SPARC construction, information is encoded in the locations of the non-zero entries of the message vector. In this paper we generalize the construction and consider modulated SPARCs, where information is encoded in both the locations and the values of the non-zero entries of the message vector. We focus on the case where the non-zero entries take values from a phase-shift keying (PSK) constellation. We propose a computationally efficient approximate message passing (AMP) decoder, and obtain analytical bounds on the state evolution parameters which predict the error performance of the decoder. Using these bounds we show that PSK-modulated SPARCs are asymptotically capacity achieving for the complex AWGN channel, with either spatial coupling or power allocation. We also provide numerical simulation results to demonstrate the error performance at finite code lengths. These results show that introducing modulation to the SPARC design can significantly reduce decoding complexity without sacrificing error performance. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

In this paper, we propose a systematic low density generator matrix (LDGM) code ensemble, which is defined by the Bernoulli process. We prove that, under maximum likelihood (ML) decoding, the proposed ensemble can achieve the capacity of binary-input output symmetric (BIOS) memoryless channels in terms of bit error rate (BER). The proof technique reveals a new mechanism, different from lowering down frame error rate (FER), that the BER can be lowered down by assigning light codeword vectors to light information vectors. The finite length performance is analyzed by deriving an upper bound and a lower bound, both of which are shown to be tight in the high signal-to-noise ratio (SNR) region. To improve the waterfall performance, we construct the systematic convolutional LDGM (SysConv-LDGM) codes by a random splitting process. The SysConv-LDGM codes are easily configurable in the sense that any rational code rate can be realized without complex optimization. As a universal construction, the main advantage of the SysConv-LDGM codes is their near-capacity performance in the waterfall region and predictable performance in the error-floor region that can be lowered down to any target as required by increasing the density of the uncoupled LDGM codes. Numerical results are also provided to verify our analysis. [ABSTRACT FROM AUTHOR]

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of guessing a sequence subject to a distortion constraint. Specifically, we assume the following game between Alice and Bob: Alice has a sequence ${x}$ of length $n$. Bob wishes to guess ${x}$ , yet he is satisfied with finding any sequence $\hat {x}$ which is within a given distortion $D$ from $x$. Thus, he successively submits queries to Alice, until receiving an affirmative answer, stating that his guess was within the required distortion. Finding guessing strategies which minimize the number of guesses (the guesswork), and analyzing its properties (e.g., its $\rho $ –th moment) has several applications in information security, source and channel coding. Guessing subject to a distortion constraint is especially useful when considering contemporary biometrically–secured systems, where the “password” which protects the data is not a single, fixed vector but rather a ball of feature vectors centered at some ${x}$ , and any feature vector within the ball results in acceptance. We formally define the guessing problem under distortion in four different setups: memoryless sources, guessing through a noisy channel, sources with memory and individual sequences. We suggest a randomized guessing strategy which is asymptotically optimal for all setups and is five–fold universal, as it is independent of the source statistics, the channel, the moment to be optimized, the distortion measure and the distortion level. [ABSTRACT FROM AUTHOR]

We study the list decodability of different ensembles of codes over the real alphabet under the assumption of an omniscient adversary. It is a well-known result that when the source and the adversary have power constraints $P $ and $N $ respectively, the list decoding capacity is equal to $\frac {1}{2}\log \frac {P}{N}$. Random spherical codes achieve constant list sizes, and the goal of the present paper is to obtain a better understanding of the smallest achievable list size as a function of the gap to capacity. We show a reduction from arbitrary codes to spherical codes, and derive a lower bound on the list size of typical random spherical codes. We also give an upper bound on the list size achievable using nested Construction-A lattices and infinite Construction-A lattices. We then define and study a class of infinite constellations that generalize Construction-A lattices and prove upper and lower bounds for the same. Other goodness properties such as packing goodness and AWGN goodness of infinite constellations are proved along the way. Finally, we consider random lattices sampled from the Haar distribution and show that if a certain conjecture that originates in analytic number theory is true, then the list size grows as a polynomial function of the gap-to-capacity. [ABSTRACT FROM AUTHOR]

A $d$ -multiplicative secret sharing ($d$ -MSS) scheme allows the players to multiply $d$ shared secrets without recovering the secrets by converting their shares locally into an additive sharing of the product. It has been proved that the $d$ -MSS among $n$ players is possible if and only if no $d$ unauthorized sets of players cover the whole set of players (type $Q_{d}$). Although this result implies some limitations on SS in the context of MPC, the $d$ -multiplicative property is still useful for simplifying complex tasks of MPC by computing the product of $d$ field elements directly and non-interactively without any setup. This paper aims to improve the usefulness of the $d$ -MSS by enhancing the security against malicious adversaries. First, we introduce the notion of verifiably multiplicative SS, verifiably MSS for short, which is mainly formalized for detecting malicious behaviors. Informally, an SS scheme is verifiably $d$ -multiplicative if the scheme is $d$ -multiplicative and further enables the players to locally generate a share of a proof that the summed value is correct (i.e., the product of $d$ shared secrets). Secondly, we prove that there is no error-free verifiably MSS scheme whose decoder of the proof is additive, and that by accepting an error probability that can be chosen arbitrarily, there exists a verifiably $d$ -MSS scheme realizing a given access structure if and only if the access structure is of type $Q_{d}$. In the proposed construction, each share of a proof consists of only two field elements. This result means that we can efficiently achieve the optimal resiliency of the standard $d$ -MSS even against malicious adversaries. We note that by allowing a general class of decoders that includes a linear one, there is an error-free verifiably $d$ -MSS scheme if the access structure is of type $Q_{d+1}$. Finally, we generalize the $d$ -multiplicative property to a $d$ -or-less version where the number $d'$ of multiplied secrets with $d'\leq d$ is not known in advance. We show that a $d$ -or-less MSS scheme can be constructed from any $d$ -MSS scheme of the same access structure with a constant overhead, and the feasibility of (verifiably) $d$ -MSS implies that of (verifiably) $d$ -or-less MSS. [ABSTRACT FROM AUTHOR]

Lattice codes are elegant and powerful structures that not only achieve the capacity of the additive white Gaussian noise (AWGN) channel but are also a key ingredient to many multiterminal schemes that exploit linearity properties. However, constructing lattice codes that can realize these benefits with low complexity is still a challenging problem. In this paper, efficient encoding and decoding algorithms are proposed for multilevel binary low-density parity-check (LDPC) lattices constructed via Construction $\text{D}'$ whose complexity is linear in the total number of coded bits. Moreover, a generalization of Construction $\text{D}'$ is proposed, which relaxes some of the nesting constraints on the parity-check matrices of the component codes, leading to a simpler and improved design. Based on this construction, low-complexity multilevel LDPC lattices are designed whose performance under multistage decoding is comparable to that of polar lattices and close to that of low-density lattice codes on the power-unconstrained AWGN channel. [ABSTRACT FROM AUTHOR]

The capacity under strong asynchronism was recently shown to be essentially unaffected by the imposed decoding delay—the elapsed time between when information is available at the transmitter and when it is decoded—and the output sampling rate. This paper shows that, in contrast with capacity, the second-order term in the maximum rate expansion is sensitive to both parameters. When the receiver must locate the sent codeword exactly and therefore achieve minimum delay equal to the blocklength $n$ , the second-order term in the maximum rate expansion is of order $\Theta (1/\rho)$ for any sampling rate $\rho =O(1/\sqrt {n})$ (and $\rho =\omega (1/n)$ for otherwise reliable communication is impossible). Instead, if $\rho =\omega (1/\sqrt {n})$ , then the second-order term is the same as under full sampling and is given by a standard $\Theta (\sqrt {n})$ term. However, if the delay constraint is only slightly relaxed to $n(1+o(1))$ , then the above order transition (for $\rho =O(1/\sqrt {n})$ and $\rho =\omega (1/\sqrt {n})$) vanishes and the second-order term remains the same as under full sampling for any $\rho =\omega (1/n)$. [ABSTRACT FROM AUTHOR]

We (people) are memory machines. Our decision processes, emotions, and interactions with the world around us are based on and driven by associations to our memories. This natural association paradigm will become critical in future memory systems, namely, the key question will not be “How do I store more information?” but rather “Do I have the relevant information? How do I retrieve it?” The focus of this paper is to make a first step in this direction. We define and solve a very basic problem in associative retrieval. Given a word $W$ , the words in the memory, which are $t$ -associated with $W$ , are the words in the ball of radius $t$ around $W$. In general, given a set of words, say $W$ , $X$ , and $Y$ , the words that are $t$ -associated with $\{W,X,Y\}$ are those in the memory that are within distance $t$ from all the three words. Our main goal is to study the maximum size of the $t$ -associated set as a function of the number of input words and the minimum distance of the words in memory—we call this value the uncertainty of an associative memory. In this paper, we consider the Hamming distance and derive the uncertainty of the associative memory that consists of all the binary vectors with an arbitrary number of input words. In addition, we study the retrieval problem, namely, how do we get the $t$ -associated set given the inputs? We note that this paradigm is a generalization of the sequences reconstruction problem that was proposed by Levenshtein (2001). In this model, a word is transmitted over multiple channels. A decoder receives all the channel outputs and decodes the transmitted word. Levenshtein computed the minimum number of channels that guarantee a successful decoder—this value happens to be the uncertainty of an associative memory with two input words. [ABSTRACT FROM AUTHOR]

Polar codes are a family of capacity-achieving codes that have explicit and low-complexity construction, encoding, and decoding algorithms. Decoding of polar codes is based on the successive-cancellation decoder, which decodes in a bit-wise manner. A decoding error occurs when at least one bit is erroneously decoded. The various codeword bits are correlated, yet performance analysis of polar codes ignores this dependence: the upper bound is based on the union bound, and the lower bound is based on the worst-performing bit. Improvement of the lower bound is afforded by considering error probabilities of two bits simultaneously. These are difficult to compute explicitly due to the large alphabet size inherent to polar codes. In this paper, we propose a method to lower-bound the error probabilities of bit pairs. We develop several transformations on pairs of synthetic channels that make the resultant synthetic channels amenable to alphabet reduction. Our method yields lower bounds that significantly improve upon currently known lower bounds for polar codes under successive-cancellation decoding. [ABSTRACT FROM AUTHOR]

In this paper, we develop a technique to extend any bound for the minimum distance of cyclic codes constructed from its defining sets (ds-bounds) to Abelian (or multivariate) codes through the notion of ${\mathbb B}$ -apparent distance. We also study conditions for an Abelian code to verify that its ${\mathbb B}$ -apparent distance reaches its (true) minimum distance. Then, we construct some codes as an application. [ABSTRACT FROM AUTHOR]

This paper investigates a multi-terminal source coding problem under a logarithmic loss fidelity which does not necessarily lead to an additive distortion measure. The problem is motivated by an extension of the information bottleneck method to a multi-source scenario where several encoders have to build cooperatively rate-limited descriptions of their sources in order to maximize information with respect to other unobserved (hidden) sources. More precisely, we study fundamental information-theoretic limits of the so-called: 1) two-way collaborative information bottleneck (TW-CIB) and 2) the collaborative distributed information bottleneck (CDIB) problems. The TW-CIB problem consists of two distant encoders that separately observe marginal (dependent) components $X_{1}$ and $X_{2}$ and can cooperate through multiple exchanges of limited information with the aim of extracting information about hidden variables $(Y_{1},Y_{2})$ , which can be arbitrarily dependent on $(X_{1},X_{2})$. On the other hand, in CDIB, there are two cooperating encoders which separately observe $X_{1}$ and $X_{2}$ and a third node which can listen to the exchanges between the two encoders in order to obtain information about a hidden variable $Y$. The relevance (figure-of-merit) is measured in terms of a normalized (per-sample) multi-letter mutual information metric (log-loss fidelity), and an interesting tradeoff arises by constraining the complexity of descriptions, measured in terms of the rates needed for the exchanges between the encoders and decoders involved. Inner and outer bounds to the complexity-relevance region of these problems are derived from which optimality is characterized for several cases of interest. Our resulting theoretical complexity-relevance regions are finally evaluated for binary symmetric and Gaussian statistical models, showing theoretical tradeoffs between the complexity-constrained descriptions and their relevance with respect to the hidden variables. [ABSTRACT FROM AUTHOR]

We consider the problem of single-round private information retrieval (PIR) from $N$ replicated databases. We consider the case when $B$ databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of $M$ messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the $T$ -privacy constraint in this paper, where any $T$ databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of correct symbols that can be retrieved privately (under the $T$ -privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be $C=(N-2B)/N \cdot (1-T/(N-2B))/(1-(T/(N-2B))^{M})$ , if $2B+T < N$. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing $2B$ databases from the system, with a penalty factor of $(N-2B)/N$ , which signifies that even though the number of databases needed for PIR is effectively $N-2B$ , the user still needs to access the entire $N$ databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the errors introduced by the Byzantine databases as opposed to erasures in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes. [ABSTRACT FROM AUTHOR]

Let $p$ be a prime, $s$ be a positive integer, and $\mathcal {R}$ be a finite commutative chain ring with the characteristic as a power of $p$. For a unit $\lambda \in \mathcal {R},~\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are ideals of the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $. In this paper, we derive necessary and sufficient conditions under which the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring. When $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring, all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are known. In this paper, we establish the algebraic structures of all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ when $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a non-chain ring. We also determine the number of codewords in each of these codes. Using their algebraic structures, we obtain symbol-pair distances, Rosenbloom–Tsfasman (RT) distances, and RT weight distributions of all constacyclic codes of length $p^{s}$ over $\mathcal {R}$. Apart from this, we derive necessary and sufficient conditions under which a constacyclic code of length $p^{s}$ over $\mathcal {R}$ is maximum-distance separable with respect to the: 1) Hamming metric; 2) symbol-pair metric; and 3) RT metric. We also provide an algorithm to decode the constacyclic codes of length $p^{s}$ over $\mathcal {R}$ using the known decoding algorithms of linear codes over finite fields with respect to the Hamming, symbol-pair, and RT metrics. [ABSTRACT FROM AUTHOR]

We consider the problem of constructing codes that can correct $\delta $ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov–Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(\delta =1)$ correcting codes and have an asymptotically optimal redundancy. Finding similar codes for $\delta \geq 2$ deletions remains an open problem. In this paper, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $\delta $ deletions (or insertions) are independent of the code word. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $\delta $ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization. [ABSTRACT FROM AUTHOR]

This paper asks how much we can gain in terms of bandwidth and user satisfaction, if recommendation systems became bandwidth aware and took into account not only the user preferences, but also the fact that they may need to serve these users under bandwidth constraints, as is the case over wireless networks. We formulate this as a new problem in the context of index coding: we relax the index coding requirements to capture scenarios where each client has preferences associated with messages. The client is satisfied to receive any message she does not already have, with a satisfaction proportional to her preference for that message. We consistently find, over a number of scenarios we sample, that although the optimization problems are in general NP-hard, significant bandwidth savings are possible even when restricted to polynomial time algorithms. [ABSTRACT FROM AUTHOR]

Quadratically constrained basis pursuit has become a popular device in sparse regularization; in particular, in the context of compressed sensing. However, the majority of theoretical error estimates for this regularizer assume an a priori bound on the noise level, which is usually lacking in practice. In this paper, we develop stability and robustness estimates, which remove this assumption. First, we introduce an abstract framework and show that the robust instance optimality of any decoder in the noise-aware setting implies stability and robustness in the noise-blind setting. This is based on certain sup-inf constants referred to as quotients, strictly related to the quotient property of compressed sensing. Then, we apply this theory to prove the robustness of quadratically constrained basis pursuit under unknown error in the cases of random Gaussian matrices and of random matrices with heavy-tailed rows, such as random sampling matrices from bounded orthonormal systems. We illustrate our results in several cases of practical importance, including subsampled Fourier measurements and the recovery of sparse polynomial expansions. [ABSTRACT FROM AUTHOR]