Abstract: Presents a listing of the editorial board, board of governors, current staff, committee members, and/or society editors for this issue of the publication. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Abstract: These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Mario Diaz;Hao Wang;Flavio P. Calmon;Lalitha Sankar;
Pages: 1949 - 1978 Abstract: Consider a data publishing setting for a dataset composed by both private and non-private features. The publisher uses an empirical distribution, estimated from $n$ i.i.d. samples, to design a privacy mechanism which is applied to new fresh samples afterward. In this paper, we study the discrepancy between the privacy-utility guarantees for the empirical distribution, used to design the privacy mechanism, and those for the true distribution, experienced by the privacy mechanism in practice. We first show that, for any privacy mechanism, these discrepancies vanish at speed $O(1/sqrt {n})$ with high probability. These bounds follow from our main technical results regarding the Lipschitz continuity of the considered information leakage measures. Then we prove that the optimal privacy mechanisms for the empirical distribution approach the corresponding mechanisms for the true distribution as the sample size $n$ increases, thereby establishing the statistical consistency of the optimal privacy mechanisms. Finally, we introduce and study uniform privacy mechanisms which, by construction, provide privacy to all the distributions within a neighborhood of the estimated distribution and, thereby, guarantee privacy for the true distribution with high probability. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Mehrdad Tahmasbi;Anne Savard;Matthieu R. Bloch;
Pages: 1979 - 2005 Abstract: The covert capacity is characterized for a non-coherent fast Rayleigh-fading wireless channel, in which a legitimate user wishes to communicate reliably with a legitimate receiver while escaping detection from a warden. It is shown that the covert capacity is achieved with an amplitude-constrained input distribution that consists of a finite number of mass points including one at zero and numerically tractable bounds are provided. It is also conjectured that distributions with two mass points in fixed locations are optimal. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Alex Dytso;Semih Yagli;H. Vincent Poor;Shlomo Shamai Shitz;
Pages: 2006 - 2022 Abstract: This paper studies an $n$ -dimensional additive Gaussian noise channel with a peak-power-constrained input. It is well known that, in this case, when $n=1$ the capacity-achieving input distribution is discrete with finitely many mass points, and when $n>1$ the capacity-achieving input distribution is supported on finitely many concentric shells. However, due to the previous proof technique, not even a bound on the exact number of mass points/shells was available. This paper provides an alternative proof of the finiteness of the number mass points/shells of the capacity-achieving input distribution while producing the first firm bounds on the number of mass points and shells, paving an alternative way for approaching many such problems. The first main result of this paper is an order tight implicit bound which shows that the number of mass points in the capacity-achieving input distribution is within a factor of two from the number of zeros of the downward shifted capacity-achieving output probability density function. Next, this implicit bound is utilized to provide a first firm upper on the support size of optimal input distribution, an $O(mathsf {A}^{2})$ upper bound where $mathsf {A}$ denotes the constraint on the input amplitude. The second main result of this paper generalizes the first one to the case when $n>1$ , showing that, for each and every dimension $nge 1$ , the number of shells that the optimal input distribution contai-s is $O(mathsf {A}^{2})$ . Finally, the third main result of this paper reconsiders the case $n=1$ with an additional average power constraint, demonstrating a similar $O(mathsf {A}^{2})$ bound. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Yi-Peng Wei;Sennur Ulukus;
Pages: 2023 - 2031 Abstract: We consider the problem of private information retrieval (PIR) of a single message out of $K$ messages from $N$ replicated and non-colluding databases where a cache-enabled user (retriever) of cache-size $S$ possesses side information in the form of uncoded portions of the messages where the message identities are unknown to the databases. The identities of these side information messages need to be kept private from the databases, i.e., we consider PIR with private side information (PSI). We characterize the optimal normalized download cost for this PIR-PSI problem under the storage constraint $S$ as $D^{*}=1+frac {1}{N}+frac {1}{N^{2}}+ {dots }+frac {1}{N^{K-1-M}}+ frac {1-r_{M}}{N^{K-M}}+frac {1-r_{M-1}}{N^{K-M+1}}+ {dots }+frac {1-r_{1}}{N^{K-1}}$ , where $M$ is the number of side information messages and $r_{i}$ is the portion of the $i$ th side information message that is cached with $sum _{i=1}^{M} r_{i}=S$ . Based on this capacity result, we prove two facts: First, for a fixed memory size $S$ and a fixed number of accessible messages $M$ , uniform caching achieves the lowest normalized download cost, i.e., $r_{i}=frac {S-{M}$ , for $i=1, {dots }, M$ , is optimum. Second, for a fixed memory size $S$ , among all possible $K-left lceil{ {S} }right rceil +1$ uniform caching schemes, the uniform caching scheme which caches $M=K$ messages achieves the lowest normalized download cost. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Swanand Kadhe;Brenden Garcia;Anoosheh Heidarzadeh;Salim El Rouayheb;Alex Sprintson;
Pages: 2032 - 2043 Abstract: We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of $K$ independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of $M$ messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is $K-M$ messages, and in the second scenario it is $lceil K/(M+1)rceil $ messages, which should be compared to $K$ messages—the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove-converse results, as well as to design achievability schemes. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Sreejith Sreekumar;Deniz Gündüz;
Pages: 2044 - 2066 Abstract: A distributed binary hypothesis testing (HT) problem involving two parties, one referred to as the observer and the other as the detector is studied. The observer observes a discrete memoryless source (DMS) and communicates its observations to the detector over a discrete memoryless channel (DMC). The detector observes another DMS correlated with that at the observer, and performs a binary hypothesis test on the joint distribution of the two DMS’s using its own observed data and the information received from the observer. The trade-off between the type I error probability and the type II error-exponent of the HT is explored. Single-letter lower bounds on the optimal type II error-exponent are obtained by using two different coding schemes, a separate HT and channel coding scheme and a joint HT and channel coding scheme based on hybrid coding for the matched bandwidth case. Exact single-letter characterization of the same is established for the special case of testing against conditional independence, and it is shown to be achieved by the separate HT and channel coding scheme. An example is provided where the joint scheme achieves a strictly better performance than the separation based scheme. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Neri Merhav;
Pages: 2067 - 2077 Abstract: In continuation to an earlier work, where error exponents of typical random codes were studied in the context of general block coding, with no underlying structure, here we carry out a parallel study on typical random, time–varying trellis codes, focusing on a certain range of low rates. By analyzing an upper bound to the error probability of the typical random trellis code, using the method of types, we first derive a Csiszár–style error exponent formula (with respect to the constraint length), which allows to characterize properties of good codes and dominant error events. We also derive a Gallager–style form, which turns out to be related to the expurgated error exponent. The main result is further extended to channels with memory and mismatch. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Sergey Tridenski;Ram Zamir;
Pages: 2078 - 2090 Abstract: We propose an algorithm for computation of the optimal correct-decoding exponent, and its corresponding optimal input. The computation algorithm translates into a stochastic iterative algorithm for adaptation of the codebook distribution to an unknown discrete memoryless channel in the limit of a large block length. The adaptation scheme uses i.i.d. random block codes, and it relies on one bit of feedback per transmitted block. Throughout the adaptation process, the communication itself is assumed reliable at a constant rate $R$ below the channel capacity $C$ . In the end of the iterations, the resulting codebook distribution guarantees reliable communication for all rates below $R + Delta $ , where $0 < Delta leq C-R$ is a predetermined reliability parameter affecting the speed of adaptation. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Anurag Anshu;Penghui Yao;
Pages: 2091 - 2114 Abstract: We consider the following communication task in the multi-party setting, which involves joint random variables $XYZMN$ with the property that $M$ is independent of $YZN$ conditioned on $X$ , and $N$ is independent of $XZM$ conditioned on $Y$ . Three parties Alice, Bob and Charlie, respectively, observe samples $x,y$ and $z$ from $XYZ$ . Alice and Bob communicate messages to Charlie with the goal that Charlie can output a sample ${ left ({m,n }right) }$ such that the distribution of ${ left ({x,y,z,m,n }right) }$ is close to $XYZMN$ . This task reflects the simultaneous message passing communication complexity. Furthermore, it is a generalization of some well studied problems in information theory, such as distributed source coding, source coding with a helper and one sender and one receiver message compression. It is also closely related to the lossy distributed source coding task. Our main result is an achievable communication region for this task in the one-shot setting, through which we obtain a nearly optimal char-cterization using auxiliary random variables of bounded size. We employ our achievability result to provide a nearly optimal one-shot communication region for the task of lossy distributed source coding, in terms of auxiliary random variables of bounded size. Finally, we show that interactions are necessary to achieve the optimal expected communication cost. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Jun Chen;Li Xie;Yameng Chang;Jia Wang;Yizhong Wang;
Pages: 2115 - 2128 Abstract: Consider a generalized multiterminal source coding system, where $binom{ell }{ m}$ encoders, each observing a distinct size- $m$ subset of $ell $ ( $ell geq 2$ ) zero-mean unit-variance exchangeable Gaussian sources with correlation coefficient $rho $ , compress their observations in such a way that a joint decoder can reconstruct the sources within a prescribed mean squared error distortion based on the compressed data. The optimal rate-distortion performance of this system was previously known only for the two extreme cases $m=ell $ (the centralized case) and $m=1$ (the distributed case), and except when $rho =0$ , the centralized system can achieve strictly lower compression rates than the distributed system under all non-trivial distortion constraints. Somewhat surprisingly, it is established in the present paper that the optimal rate-distortion performance of the afore-described generalized multiterminal source coding system with $mgeq 2$ coincides with that of the centralized system for all distortions when $rho leq 0$ and for distortions below an explicit positive threshold (depending on $m$ ) when $rho> 0- . Moreover, when $rho> 0$ , the minimum achievable rate of generalized multiterminal source coding subject to an arbitrary positive distortion constraint $d$ is shown to be within a finite gap (depending on $m$ and $d$ ) from its centralized counterpart in the large $ell $ limit except for possibly the critical distortion $d=1-rho $ . PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Kun Fang;Xin Wang;Marco Tomamichel;Mario Berta;
Pages: 2129 - 2140 Abstract: We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are given by semidefinite programs. Second, we introduce the channel’s smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel’s smooth max-information as the one-shot quantum simulation cost under no-signalling assisted codes, which significantly simplifies the study of channel simulation and provides insights and bounds for the case under entanglement-assisted codes. Third, we derive the asymptotic equipartition property of the channel’s smooth max-information; i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem in the presence of no-signalling correlations. Finally, we explore the simulation cost of various quantum channels. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Farzin Salek;Anurag Anshu;Min-Hsiu Hsieh;Rahul Jain;Javier Rodríguez Fonollosa;
Pages: 2141 - 2164 Abstract: We study the communication capabilities of a quantum channel under the most general channel model known as the one-shot model. Unlike classical channels that can only be used to transmit classical information (bits), a quantum channel can be used for transmission of classical information, quantum information (qubits) and simultaneous transmission of classical and quantum information. In this work, we investigate the one-shot capabilities of a quantum channel for simultaneously transmitting bits and qubits. This problem was studied in the asymptotic regime for a memoryless channel where a regularized characterization of the capacity region was reported. It is known that the transmission of private classical information is closely related to the problem of quantum information transmission. We resort to this idea and find achievable and converse bounds on the simultaneous transmission of the public and private classical information. Then shifting the classical private rate to the quantum information rate leads to a rate region for simultaneous transmission of classical and quantum information. In the case of asymptotic i.i.d. setting, our one-shot result is evaluated to the known results in the literature. Our main tools used in the achievability proofs are position-based decoding and convex-split lemma. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Ludovico Lami;
Pages: 2165 - 2183 Abstract: We compute on all quantum states several measures that characterise asymptotic quantum coherence manipulation under restricted classes of operations. We focus on the distillable coherence, i.e. the maximum rate of production of approximate pure bits of coherence starting from independent copies of an input state $ {rho }$ , and on the coherence cost, i.e. the minimum rate of consumption of pure coherence bits that is needed to generate many copies of $ {rho }$ with vanishing error. We obtain the first closed-form expression for the distillable coherence under strictly incoherent operations (SIO), proving that it coincides with that obtained via physically incoherent operations (PIO). This shows that SIO and PIO are equally weak at distilling coherence, sheds light on the recently discovered phenomenon of generic bound coherence, and provides us with an explicit optimal distillation protocol that is amenable to practical implementations. We give a single-letter formula for the coherence cost under PIO, showing that it is finite on a set of states with nonzero volume. Since PIO can be realised in a laboratory with incoherent ancillae, unitaries, and measurements, our result puts fundamental limitations on coherence manipulation in an experimentally relevant setting. We find examples of ‘abyssally bound’ states with vanishing PIO distillable coherence yet infinite PIO coherence cost. Our findings complete the picture of asymptotic coherence manipulation under all the main classes of incoherent operations. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Milad Johnny;Mohammad Reza Aref;
Pages: 2184 - 2197 Abstract: In this paper, we consider the problem of data transmission for ${K}-$ user interference channel (IC) with no channel state information (CSI) at transmitters. Each pair of transceivers with the aid of a particular precoder and a switching pattern structure tries to place its desired signal in a subspace which is linearly independent of interference signals. We show that if the channel values are known only to the receivers, the sum degrees-of-freedom (DoF) of the linear interference alignment (IA) with reconfigurable antenna at receivers is $frac {{ { Kr}}}{ {r}^{2}- {r}+ {K}}$ , where $ {r} = left lceil{ {frac {sqrt {1+4 {K}}-1}{2}} }right rceil $ . For previous methods when $3 leq {K} leq 10^{4}$ , the number of solvable problems to achieve maximum sum DoF is less than 2% of different cases while in our work there is not any limitation on the number of users. In comparison with the previous related works in our proposed method, there is no limit on the number of users and the reception modes. The result indicates that the maximum sum DoF for the ${K}-$ user IC with asymptotically large values of K is $frac {sqrt { {K}}}{2}$ . Thus, the sum DoF of such networks using the reconfigurable antenna at receivers grows sublinearly with the number of users, whereas it grows linearly in the case where transmitters have access to CSI. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Yimin Pang;Mahesh K. Varanasi;
Pages: 2198 - 2218 Abstract: The MAC-IC-MAC is a class of multiple-access interference channels consisting of two multiple-access channels (MACs) that are mutually interfering but in which there is interference only from one transmitter of each MAC to the receiver of the other MAC. Two achievable rate regions that are within a quantifiable gap of the capacity region for the discrete-memoryless semi-deterministic MAC-IC-MAC were obtained in a previous companion work by the authors using inner and outer bounds that are unions of polytopes over admissible random coding distributions. In this paper, we obtain single-distribution—and hence explicit—inner and outer bounds that characterize the capacity region of the MIMO Gaussian MAC-IC-MAC to within a constant gap. We also evaluate and study the generalized degrees of freedom (GDoF) region via multidimensional signal-level partitioning for MIMO networks. Through its lens, the achievability of the key vertices of the GDoF region are examined. This analysis as well as the symmetric GDoF curve reveal that, at high SNR, when the ratio of the interference-to-noise to the signal-to-noise ratios, both taken in dB, is within a certain range, non-interfering transmitters in that cell can fully occupy the receivers’ signal partitions in one or more dimensions that cannot otherwise be utilized by the interfering transmitter alone. This extends the same finding in the companion paper which established the results of this work for the scalar Gaussian MAC-IC-MAC. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Parisa Hassanzadeh;Antonia M. Tulino;Jaime Llorca;Elza Erkip;
Pages: 2219 - 2251 Abstract: This paper studies the fundamental limits of content delivery in a cache-aided broadcast network for correlated content generated by a discrete memoryless source with arbitrary joint distribution. Each receiver is equipped with a cache of equal capacity, and the requested files are delivered over a shared error-free broadcast link. A class of achievable correlation-aware schemes based on a two-step source coding approach is proposed. Library files are first compressed, and then cached and delivered using a combination of multiple-request caching schemes that are agnostic to the content correlations. The first step uses Gray-Wyner source coding to represent the library via private descriptions and descriptions that are common to more than one file. The second step then becomes a multiple-request caching problem, where the demand structure is dictated by the configuration of the compressed library, and it is interesting in its own right. The performance of the proposed two-step scheme is evaluated by comparing its achievable rate with a lower bound on the optimal peak and average rate-memory trade-offs in a two-file multiple-receiver network, and in a three-file two-receiver network. Specifically, in a network with two files and two receivers, the achievable rate matches the lower bound for a significant memory regime and it is within half of the conditional entropy of files for all other memory values. In the three-file two-receiver network, the two-step strategy achieves the lower bound for large cache capacities, and it is within half of the joint entropy of two of the sources conditioned on the third one for all other cache sizes. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Emanuele Parrinello;Ayşe Ünsal;Petros Elia;
Pages: 2252 - 2268 Abstract: The work explores the fundamental limits of coded caching in the setting where a transmitter with potentially multiple ( $N_{0}$ ) antennas serves different users that are assisted by a smaller number of caches. Under the assumption of uncoded cache placement, the work derives the exact optimal worst-case delay and DoF, for a broad range of user-to-cache association profiles where each such profile describes how many users are helped by each cache. This is achieved by presenting an information-theoretic converse based on index coding that succinctly captures the impact of the user-to-cache association, as well as by presenting a coded caching scheme that optimally adapts to the association profile by exploiting the benefits of encoding across users that share the same cache. The work reveals a powerful interplay between shared caches and multiple senders/antennas, where we can now draw the striking conclusion that, as long as each cache serves at least $N_{0}$ users, adding a single degree of cache-redundancy can yield a DoF increase equal to $N_{0}$ , while at the same time — irrespective of the profile — going from 1 to $N_{0}$ antennas reduces the delivery time by a factor of $N_{0}$ . Finally some conclusions are also drawn for the related problem of coded caching with multiple file requests. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Yijin Zhang;Yi Chen;Yuan-Hsun Lo;Wing Shing Wong;
Pages: 2269 - 2279 Abstract: The collision channel without feedback (CCw/oFB) introduced by Massey and Mathys, depicts a scenario where multiple users share a communication channel but have arbitrary time offsets, and can never learn these time offsets due to the lack of feedback. This paper considers an extension of the CCw/oFB, which allows the receiver to use successive interference cancellation (SIC) to cancel the interference caused by those collided packets whose contents have been known by the receiver. We derive the zero-packet-loss throughput regions of this model for both the unsynchronized and slot-synchronized cases. Given an arbitrary number of users and a packet alphabet of arbitrary size, it is shown that these two regions coincide, and the outer boundary of this common region is the set of all points with only nonnegative components that add up to one. It is further shown that all points on this outer boundary with only rational components can be achieved without packet loss in the slot-synchronized case. The constructive proofs are based on a joint design of protocol sequences, identification/location algorithm and erasure correcting codes. These findings indicate that the negative impact of the lack of time synchronization on the throughput performance can be removed by the help of SIC. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Shaofeng Zou;Venugopal V. Veeravalli;Jian Li;Don Towsley;
Pages: 2280 - 2295 Abstract: The problem of quickest detection of dynamic events in networks is studied. At some unknown time, an event occurs, and a number of nodes in the network are affected by the event, in that they undergo a change in the statistics of their observations. It is assumed that the event is dynamic, in that it can propagate along the edges in the network, and affect more and more nodes with time. The event propagation dynamics is assumed to be unknown. The goal is to design a sequential algorithm that can detect a “significant” event, i.e., when the event has affected no fewer than $eta $ nodes, as quickly as possible, while controlling the false alarm rate. Fully connected networks are studied first, and the results are then extended to arbitrarily connected networks. The designed algorithms are shown to be adaptive to the unknown propagation dynamics, and their first-order asymptotic optimality is demonstrated as the false alarm rate goes to zero. The algorithms can be implemented with linear computational complexity in the network size at each time step, which is critical for online implementation. Numerical simulations are provided to validate the theoretical results. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Sihem Mesnager;Ahmet Sınak;
Pages: 2296 - 2310 Abstract: Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. There are several methods to construct linear codes, one of which is based on functions over finite fields. Recently, many construction methods for linear codes from functions have been proposed in the literature. In this paper, we generalize the recent construction methods given by Tang et al. in [IEEE Transactions on Information Theory, 62(3), 1166-1176, 2016] to weakly regular plateaued functions over finite fields of odd characteristic. We first construct three-weight linear codes from weakly regular plateaued functions based on the second generic construction and then determine their weight distributions. We also give a punctured version and subcode of each constructed code. We note that they may be (almost) optimal codes and can be directly employed to obtain (democratic) secret sharing schemes, which have diverse applications in the industry. We next observe that the constructed codes are minimal for almost all cases and finally describe the access structures of the secret sharing schemes based on their dual codes. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Pengfei Huang;Yi Liu;Xiaojie Zhang;Paul H. Siegel;Erich F. Haratsch;
Pages: 2311 - 2330 Abstract: Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances, and we discuss decoding algorithms and correctable patterns of errors and erasures. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes, generalizing a recent construction of capacity-achieving rate-compatible polar codes. Applications of rate-compatible codes to data storage are considered. We design two-level rate-compatible codes based on Bose-Chaudhuri-Hocquenghem (BCH) and low-density parity-check (LDPC) codes which are two popular codes widely used in the data storage industry, and then we evaluate the performance of these codes in multi-level cell (MLC) flash memories. We also examine code performance on binary and $q$ -ary symmetric channels. Finally, we briefly discuss two variations of our main construction and their relative performance. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Andreas Lenz;Paul H. Siegel;Antonia Wachter-Zeh;Eitan Yaakobi;
Pages: 2331 - 2351 Abstract: In this paper we study error-correcting codes for the storage of data in synthetic deoxyribonucleic acid (DNA). We investigate a storage model where a data set is represented by an unordered set of $M$ sequences, each of length $L$ . Errors within that model are a loss of whole sequences and point errors inside the sequences, such as insertions, deletions and substitutions. We derive Gilbert-Varshamov lower bounds and sphere packing upper bounds on achievable cardinalities of error-correcting codes within this storage model. We further propose explicit code constructions than can correct errors in such a storage system that can be encoded and decoded efficiently. Comparing the sizes of these codes to the upper bounds, we show that many of the constructions are close to optimal. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Venkatesan Guruswami;Ray Li;
Pages: 2352 - 2374 Abstract: We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining ${p}_{0}^{(adv)}$ , the zero-rate threshold of adversarial deletions, defined to be the supremum of all $p$ for which there exists a code family with rate bounded away from 0 capable of correcting a fraction $p$ of adversarial deletions. A recent construction of deletion-correcting codes shows that ${p}_{0}^{(adv)} ge sqrt {2}-1$ , and the trivial upper bound, ${p}_{0}^{(adv)}le {1}/{2}$ , is the best known. Perhaps surprisingly, we do not know whether or not ${p}_{0}^{(adv)} = 1/2$ . In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of ${pn}$ deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction ${p} < 1$ of oblivious deletions, establishing that the associated zero-rate threshold ${p}_{0}^{(obliv)}$ equals 1. For online deletions, where the channel decides whether to delete bit ${x}_{{i}}$ based only on knowledge of bits ${x}_{1}{x}_{2} {dots }{x}_{{i}}$ , define the deterministic zero-rate threshold for online deletions ${p}_{0}^{(on,{d})}$ to be the supremum of $p$ for which there exist deterministic codes against an online channel causing ${pn}$ deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove ${p}_{0}^{(adv)}={1}/{2}$ if and only if ${p}_{0}^{(on,{d})}={1}/{2}$ . PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Jin Sima;Netanel Raviv;Jehoshua Bruck;
Pages: 2375 - 2391 Abstract: Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov-Tenengolts construction. Our techniques require $7log ({n})+ {o}(log ({n}))$ redundant bits to encode an n-bit message, which is closer to optimal than previous constructions. Moreover, the encoding and decoding algorithms have ${O}({n})$ time complexity. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Jun Zhang;Daqing Wan;Krishna Kaipa;
Pages: 2392 - 2401 Abstract: Projective Reed-Solomon (PRS) codes are Reed-Solomon codes of the maximum possible length $q+1$ . The classification of deep holes –received words with maximum possible error distance– for PRS codes is an important and difficult problem. In this paper, we use algebraic methods to explicitly construct three classes of deep holes for PRS codes. We show that these three classes completely classify all deep holes of PRS codes with redundancy four. Previously, the deep hole classification was only known for PRS codes with redundancy at most three. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Han Cai;Ying Miao;Moshe Schwartz;Xiaohu Tang;
Pages: 2402 - 2416 Abstract: Locally repairable codes are desirable for distributed storage systems to improve the repair efficiency. In this paper, a new combination of codes with locality and codes with multiple disjoint repair sets (also called availability) is introduced. Accordingly, a Singleton-type bound is derived for the new code, which contains those bounds in [9], [20], [28] as special cases. Optimal constructions are proposed with respect to the new bound. In addition, these constructions can also generate optimal codes with multiple disjoint repair sets with respect to the bound in [28], which to the best of our knowledge, are the first explicit constructions that can achieve the bound in [28]. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Lukas Holzbaur;Ragnar Freij-Hollanti;Antonia Wachter-Zeh;Camilla Hollanti;
Pages: 2417 - 2429 Abstract: Recently, information-theoretic private information retrieval (PIR) from coded storage systems has gained a lot of attention, and a general star product PIR scheme was proposed. In this paper, the star product scheme is adopted, with appropriate modifications, to the case of private (e.g., video) streaming. It is assumed that the files to be streamed are stored on $n$ servers in a coded form, and the streaming is carried out via a convolutional code. The star product scheme is defined for this special case, and various properties are analyzed for two channel models related to straggling and Byzantine servers, both in the baseline case as well as with colluding servers. The achieved PIR rates for the given models are derived and, for the cases where the capacity is known, the first model is shown to be asymptotically optimal, when the number of stripes in a file is large. The second scheme introduced in this work is shown to be the equivalent of block convolutional codes in the PIR setting. For the Byzantine server model, it is shown to outperform the trivial scheme of downloading stripes of the desired file separately without memory. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Mao-Ching Chiu;
Pages: 2430 - 2442 Abstract: By inserting interleavers between intermediate stages of the polar encoder, a new class of polar codes, termed interleaved polar (i-polar) codes, is proposed. By the uniform interleaver assumption, we derive the weight enumerating function (WEF) and the input-output weight enumerating function (IOWEF) averaged over the ensemble of i-polar codes. The average WEF can be used to calculate the upper bound on the average block error rate (BLER) of a code selected at random from the ensemble of i-polar codes. Also, we propose a concatenated coding scheme that employs $P$ high rate codes as the outer code and $Q$ i-polar codes as the inner code with an interleaver in between. The average WEF of the concatenated code is derived based on the uniform interleaver assumption. Simulation results show that BLER upper bounds can well predict BLER performance levels of the concatenated codes. The results show that the performance of the proposed concatenated code with $P=Q=2$ is better than that of the CRC-aided i-polar code with $P=Q=1$ of the same length and code rate at high signal-to-noise ratios (SNRs). Moreover, the proposed concatenated code allows multiple decoders to operate in parallel, which can reduce the decoding latency and hence is suitable for ultra-reliable low-latency communications (URLLC). PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Rafael G. L. D’Oliveira;Salim El Rouayheb;
Pages: 2443 - 2455 Abstract: We study a class of private information retrieval (PIR) methods that we call one-shot schemes. The intuition behind one-shot schemes is the following. The user’s query is regarded as a dot product of a query vector and the message vector (database) stored at multiple servers. Privacy, in an information theoretic sense, is then achieved by encrypting the query vector using a secure linear code, such as secret sharing. Several PIR schemes in the literature, in addition to novel ones constructed here, fall into this class. One-shot schemes provide an insightful link between PIR and data security against eavesdropping. However, their download rate is not optimal, i.e., they do not achieve the PIR capacity. Our main contribution is two transformations of one-shot schemes, which we call refining and lifting. We show that refining and lifting one-shot schemes gives capacity-achieving schemes for the cases when the PIR capacity is known. In the other cases, when the PIR capacity is still unknown, refining and lifting one-shot schemes gives, for most parameters, the best download rate so far. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Minjia Shi;Denis S. Krotov;Patrick Solé;
Pages: 2456 - 2465 Abstract: The dual of the Kasami code of length $q^{2}-1$ , with $q$ a power of 2, is constructed by concatenating a cyclic MDS code of length $q+1$ over $F_{q}$ with a Simplex code of length $q-1$ . This yields a new derivation of the weight distribution of the Kasami code, a new description of its coset graph, and a new proof that the Kasami code is completely regular. The automorphism groups of the Kasami code and the related $q$ -ary MDS code are determined. New cyclic completely regular codes over finite fields a power of 2, generalized Kasami codes, are constructed; they have coset graphs isomorphic to that of the Kasami codes. Another wide class of completely regular codes, including additive codes, as well as unrestricted codes, is obtained by combining cosets of the Kasami or generalized Kasami code. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Yauhen Yakimenka;Eirik Rosnes;
Pages: 2466 - 2486 Abstract: In this work, we perform a complete failure analysis of the interval-passing algorithm (IPA) for compressed sensing. The IPA is an efficient iterative algorithm for reconstructing a $k$ -sparse nonnegative $n$ -dimensional real signal ${x}$ from a small number of linear measurements ${y}$ . In particular, we show that the IPA fails to recover ${x}$ from ${y}$ if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance to the success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover ${x}$ if and only if the support of ${x}$ contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Two heuristics to locate small-size termatiko sets are presented. For binary column-regular measurement matrices with no 4-cycles, we provide a lower bound on the termatiko distance, defined as the smallest size of a nonempty termatiko set. For measurement matrices constructed from the parity-check matrices of array low-density parity-check codes, upper bounds on the termatiko distance equal to half the best known upper bound on the minimum distance are provided for column-weight at most 7, while for column-weight 3, the exact termatiko distance and-its corresponding multiplicity are provided. Next, we show that adding redundant rows to the measurement matrix does not create new termatiko sets, but rather potentially removes termatiko sets and thus improves performance. An algorithm is provided to efficiently search for such redundant rows. Finally, we present numerical results for different specific measurement matrices and also for protograph-based ensembles of measurement matrices, as well as simulation results of IPA performance, showing the influence of small-size termatiko sets. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Christos Thrampoulidis;Ankit Singh Rawat;
Pages: 2487 - 2500 Abstract: In the problem of structured signal recovery from high-dimensional linear observations, it is commonly assumed that full-precision measurements are available. Under this assumption, the recovery performance of the popular Generalized Lasso (G-Lasso) is by now well-established. In this paper, we extend these types of results to the practically relevant settings with quantized measurements. We study two extremes of the quantization schemes, namely, uniform and one-bit quantization; the former imposes no limit on the number of quantization bits, while the second only allows for one bit. In the presence of a uniform dithering signal and when measurement vectors are sub-gaussian, we show that the same algorithm (i.e., the G-Lasso) has favorable recovery guarantees for both uniform and one-bit quantization schemes. Our theoretical results, shed light on the appropriate choice of the range of values of the dithering signal and accurately capture the error dependence on the problem parameters. For example, our error analysis shows that the G-Lasso with one-bit uniformly dithered measurements leads to only a logarithmic rate loss compared to the full-precision measurements. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Dennis Amelunxen;Martin Lotz;Jake Walvin;
Pages: 2501 - 2516 Abstract: We derive bounds relating Renegar’s condition number to quantities that govern the statistical performance of convex regularization in settings that include the $ell _{1}$ -analysis setting. Using results from conic integral geometry, we show that the bounds can be made to depend only on a random projection, or restriction, of the analysis operator to a lower dimensional space, and can still be effective if these operators are ill-conditioned. As an application, we get new bounds for the undersampling phase transition of composite convex regularizers. Key tools in the analysis are Slepian’s inequality and the kinematic formula from integral geometry. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Mohamed Ndaoud;Alexandre B. Tsybakov;
Pages: 2517 - 2532 Abstract: In the context of high-dimensional linear regression models, we propose an algorithm of exact support recovery in the setting of noisy compressed sensing where all entries of the design matrix are independent and identically distributed standard Gaussian. This algorithm achieves the same conditions of exact recovery as the exhaustive search (maximal likelihood) decoder, and has an advantage over the latter of being adaptive to all parameters of the problem and computable in polynomial time. The core of our analysis consists in the study of the non-asymptotic minimax Hamming risk of variable selection. This allows us to derive a procedure, which is nearly optimal in a non-asymptotic minimax sense. Then, we develop its adaptive version, and propose a robust variant of the method to handle datasets with outliers and heavy-tailed distributions of observations. The resulting polynomial time procedure is near optimal, adaptive to all parameters of the problem and also robust. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Michael Brand;
Pages: 2533 - 2548 Abstract: Strict Minimum Message Length (SMML) is an information-theoretic statistical inference method widely cited (but only with informal arguments) as providing estimations that are consistent for general estimation problems. It is, however, almost invariably intractable to compute, for which reason only approximations of it (known as MML algorithms) are ever used in practice. Using novel techniques that allow for the first time direct, non-approximated analysis of SMML solutions, we investigate the Neyman-Scott estimation problem, an oft-cited showcase for the consistency of MML, and show that even with a natural choice of prior neither SMML nor its popular approximations are consistent for it, thereby providing a counterexample to the general claim. This is the first known explicit construction of an SMML solution for a natural, high-dimensional problem. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Arun Padakandla;P. R. Kumar;Wojciech Szpankowski;
Pages: 2549 - 2569 Abstract: As an increasing amount of data is gathered nowadays and stored in databases, the question arises of how to protect the privacy of individual records in a database even while providing accurate answers to queries on the database. Differential Privacy (DP) has gained acceptance as a framework to quantify vulnerability of algorithms to privacy breaches. We consider the problem of how to sanitize an entire database via a DP mechanism, on which unlimited further querying is performed. While protecting privacy, it is important that the sanitized database still provide accurate responses to queries. The central contribution of this work is to characterize the amount of information preserved in an optimal DP database sanitizing mechanism (DSM). We precisely characterize the utility-privacy trade-off of mechanisms that sanitize databases in the asymptotic regime of large databases. We study this in an information-theoretic framework by modeling a generic distribution on the data, and a measure of fidelity between the histograms of the original and sanitized databases. We consider the popular $mathbb {L}_{1}-$ distortion metric, i.e., the total variation norm that leads to the formulation as a linear program (LP). This optimization problem is prohibitive in complexity with the number of constraints growing exponentially in the parameters of the problem. Our focus on the asymptotic regime enables us characterize precisely, the limit of the sequence of solutions to this optimization problem. Leveraging tools from discrete geometry, analytic combinatorics, and duality theorems of optimization, we fully characterize this limit in terms of a power series whose coefficients are the number of integer points on a multidimensional convex cross-polytope studied by Ehrhart in 1967. Employing Ehrhart theory, we determine a simple closed form computable expression for the asymptotic growth of the optimal privacy-fi-elity trade-off to infinite precision. At the heart of the findings is a deep connection between the minimum expected distortion and a fundamental construct in Ehrhart theory - Ehrhart series of an integral convex polytope. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Lakshmi Kanta Patra;Suchandan Kayal;Somesh Kumar;
Pages: 2570 - 2580 Abstract: There are various situations where prior information is available on parameters in the form of order relations. One needs to take into account this information to obtain superior estimators. Shannon modeled uncertainty mathematically and called it entropy. In this paper, we study the problem of estimating entropy of two exponential populations associated with a common scale parameter, and unknown but ordered location parameters. In particular, the unrestricted best affine equivariant estimator is shown to be inadmissible under order restricted location parameters with respect to a class of location invariant loss functions. Under some specific location invariant loss functions, various improved estimators are obtained. Applications of this problem are developed for various sampling schemes: $(i)$ i.i.d. sampling, $(ii)$ record values, $(iii)$ Type-II censoring and $(iv)$ progressive Type-II censoring. Numerically, we have compared the risk performance of the proposed estimators for the squared error and linex loss functions. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Sung-Il Pae;
Pages: 2581 - 2587 Abstract: An $m$ -extracting procedure produces unbiased random bits from a loaded dice with $m$ faces, and its output rate, the average number of output per input is bounded by the Shannon entropy of the source. This information-theoretic upper bound can be achieved only asymptotically as the input size increases, by certain extracting procedures that we call asymptotically optimal. Although a computationally efficient asymptotically optimal 2-extracting procedure has been known for a while, its counterparts for $m$ -ary input, $m>2$ , was found only recently, and they are still relatively complicated to describe. A binarization takes inputs from an $m$ -faced dice and produce bit sequences to be fed into a binary extracting procedure to obtain random bits. Thus, binary extracting procedures give rise to an $m$ -extracting procedure via a binarization. A binarization is to be called complete, if it preserves the asymptotic optimality, and such a procedure has been proposed by Zhou and Bruck. We show that a complete binarization naturally arises from a binary tree with $m$ leaves. Therefore, there exist complete binarizations in abundance and Zhou-Bruck scheme is an instance of them. We now have a relatively simple way to obtain an asymptotically optimal and computationally efficient $m$ -extracting procedure, from a binary one, because these-binarizations are both conceptually and computationally simple. The well-known leaf entropy theorem and a closely related structure lemma play important roles in the arguments. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Zhe Li;San Ling;Chaoping Xing;Sze Ling Yeo;
Pages: 2588 - 2598 Abstract: In this paper, we propose new classes of trapdoor functions to solve the bounded distance decoding problem in lattices. Specifically, we construct lattices based on properties of polynomials for which the bounded distance decoding problem is hard to solve unless some trapdoor information is revealed. We thoroughly analyze the security of our proposed functions using state-of-the-art attacks and results on lattice reductions. Finally, we describe how our functions can be used to design quantum-safe encryption schemes with reasonable public key sizes. Our encryption schemes are efficient with respect to key generation, encryption and decryption. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)

Authors:
Lei Yu;Vincent Y. F. Tan;
Pages: 2599 - 2608 Abstract: In this correspondence, we correct an erroneous result on the achievability part of the Rényi common information with order $1+sin (1,2]$ in (L. Yu and V. Y. F. Tan, “Wyner’s common information under Rényi divergence measures,” IEEE Trans. Inf. Theory, vol. 64, no. 5, pp. 3616–3632, May 2018). The new achievability result (upper bound) of the Rényi common information no longer coincides with Wyner’s common information. We also provide a new converse result (lower bound) in this correspondence for the Rényi common information with order $1+sin (1,infty]$ . Numerical results show that for doubly symmetric binary sources, the new upper and lower bounds coincide for the order $1+sin (1,2]$ and they are both strictly larger than Wyner’s common information for this case. PubDate:
April 2020
Issue No:Vol. 66, No. 4 (2020)