Search

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and has numerous practical applications. One of the defining features of group testing is whether the tests are adaptive (i.e., a given test can be chosen based on all previous outcomes) or non-adaptive (i.e., all tests must be chosen in advance). In this paper, building on the success of binary splitting techniques in noiseless group testing (Hwang, 1972), we introduce noisy group testing algorithms that apply noisy binary search as a subroutine. We provide three variations of this approach with increasing complexity, culminating in an algorithm that succeeds using a number of tests that matches the best known previously (Scarlett, 2019), while overcoming fundamental practical limitations of the existing approach, and more precisely capturing the dependence of the number of tests on the error probability. We provide numerical experiments demonstrating that adaptive group testing strategies based on noisy binary search can be highly effective in practice, using significantly fewer tests compared to state-of-the-art non-adaptive strategies. [ABSTRACT FROM AUTHOR]

A $((k,n))$ quantum threshold secret sharing (QTS) scheme is a quantum cryptographic protocol for sharing a quantum secret among $n$ parties such that the secret can be recovered by any $k$ or more parties while $k-1$ or fewer parties have no information about the secret. Despite extensive research on these schemes, there has been very little study on optimizing the quantum communication cost during recovery. Recently, we initiated the study of communication efficient quantum threshold secret sharing (CE-QTS) schemes. These schemes reduce the communication complexity in QTS schemes by accessing $d>k$ parties for recovery; here $d$ is fixed ahead of encoding the secret. In contrast to the standard QTS schemes which require $k$ qudits for recovering each qudit in the secret, these schemes have a lower communication cost of $\frac {d}{d-k+1}$. In this paper, we further develop the theory of communication efficient quantum threshold schemes. Here, we propose universal CE-QTS schemes which reduce the communication cost for all $d>k$ simultaneously. We provide a framework based on ramp quantum secret sharing to construct CE-QTS and universal CE-QTS schemes. We give another construction for universal CE-QTS schemes based on Staircase codes. We derived a lower bound on communication complexity and show that our constructions are optimal. Finally, an information theoretic model is developed to analyse CE-QTS schemes and the lower bound on communication complexity is proved again using this model. [ABSTRACT FROM AUTHOR]

Let $ \mathbb K$ be an algebraically closed field. In this paper, we consider the class of smooth plane curves of degree $n+1>3$ over $ \mathbb K$ , containing three points, $P_{1},P_{2}$ , and $P_{3}$ , such that $nP_{1}+P_{2}$ , $nP_{2}+P_{3}$ , and $nP_{3}+P_{1}$ are divisors cut out by three distinct lines. For such curves, we determine the dimension of certain special divisors supported on $\{P_{1},P_{2},P_{3}\}$ , as well as an explicit description of all pure gaps at each nonempty subset of the distinguished points $P_{1},P_{2}$ , and $P_{3}$. When $ \mathbb K=\overline { \mathbb F}_{q}$ , this class of curves, which includes the Hermitian curve, is used to construct algebraic geometry codes having minimum distance better than the Goppa bound. [ABSTRACT FROM AUTHOR]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [ABSTRACT FROM AUTHOR]

The mutual information (MI) of Gaussian multi-input multi-output (MIMO) channels has been evaluated by utilizing random matrix theory (RMT) and shown to asymptotically follow Gaussian distribution, where the ergodic mutual information (EMI) converges to a deterministic quantity. However, with non-Gaussian channels, there is a bias between the EMI and its deterministic equivalent (DE), whose evaluation is not available in the literature. This bias of the EMI is related to the bias for the trace of the resolvent in large RMT. In this paper, we first derive the bias for the trace of the resolvent, which is further extended to compute the bias for the linear spectral statistics (LSS). Then, we apply the above results on non-Gaussian MIMO channels to determine the bias for the EMI. It is also proved that the bias for the EMI is −0.5 times of that for the variance of the MI. Finally, the derived bias is utilized to modify the central limit theory (CLT) and calculate the outage probability. Numerical results show that the modified CLT significantly outperforms previous methods in approximating the distribution of the MI and improves the accuracy for the outage probability evaluation. [ABSTRACT FROM AUTHOR]

In this paper we consider the diversity-multiplexing gain tradeoff (DMT) of so-called minimum delay asymmetric space-time codes for the $n \times m$ MIMO channel. Such codes correspond to lattices in $M_{n}(\mathbb {C})$ with dimension smaller than $2n^{2}$. Currently, very little is known about their DMT, except in the case $m=1$ , corresponding to the multiple input single output (MISO) channel. Further, apart from the MISO case, no DMT optimal asymmetric codes are known. We first discuss previous criteria used to analyze the DMT of space-time codes and comment on why these methods fail when applied to asymmetric codes. We then consider two special classes of asymmetric codes where the code-words are restricted to either real or quaternion matrices. We prove two separate diversity-multiplexing gain trade-off (DMT) upper bounds for such codes and provide a criterion for a lattice code to achieve these upper bounds. We also show that lattice codes based on $\mathbb {Q}$ -central division algebras satisfy this optimality criterion. As a corollary this result provides a DMT classification for all $\mathbb {Q}$ -central division algebra codes that are based on standard embeddings. While the $\mathbb {Q}$ -central division algebra based codes achieve the largest possible DMT of a code restricted to either real or quaternion space, they still fall short of the optimal DMT apart from the MISO case. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

The article announces that Marco Dalai, electronic engineer, has received the 2014 Institute of Electrical and Electronics Engineers (IEEE) Information Theory Society Paper Award, for the paper "Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels" in December 2013.

This paper investigates the Gaussian state-dependent interference channel (IC) and Z-IC, in which two receivers are corrupted respectively by two different but correlated states that are noncausally known to two transmitters but are unknown to the receivers. Three interference regimes are studied, and the capacity region boundary or the sum capacity boundary is characterized either fully or partially under various channel parameters. In particular, the impact of the correlation between states on cancellation of state and interference as well as achievability of capacity is explored with numerical illustrations. For the very strong interference regime, the capacity region is achieved by the scheme where the two transmitters implement a cooperative dirty paper coding. For the strong but not very strong interference regime, the sum-rate capacity is characterized by rate splitting, layered dirty paper coding, and successive cancellation. For the weak interference regime, the sum-rate capacity is achieved via dirty paper coding individually at two receivers as well as treating interference as noise. This paper also provides the achievable region for the state-dependent IC with each state known at its corresponding transmitter. [ABSTRACT FROM AUTHOR]

Vector linear solvability of non-multicast networks depends upon both the characteristic of the finite field and the dimension of the vector linear network code. In the literature, the dependency on the characteristic of the finite field and the dependency on the dimension have been studied separately. In this paper, we show the interdependency between the characteristic of the finite field and the dimension of the vector linear network code that achieves a vector linear network coding (VLNC) solution in non-multicast networks. For any given network $\mathcal {N}$ , we define $P(\mathcal {N},d)$ as the set of all characteristics of finite fields over which the network $\mathcal {N}$ has a $d$ -dimensional VLNC solution. To the best of our knowledge, for any network $\mathcal {N}$ shown in the literature, if $P(\mathcal {N},1)$ is non-empty, then $P(\mathcal {N},1) = P(\mathcal {N},d)$ for any positive integer $d$. We show that, for any two non-empty sets of primes $P_{1}$ and $P_{2}$ , there exists a network $\mathcal {N}$ such that $P(\mathcal {N},1) = P_{1}$ , but $P(\mathcal {N},2) = \{P_{1},P_{2} \}$. We also show that there are networks exhibiting a similar advantage (the existence of a VLNC solution over a larger set of characteristics) if the dimension is increased from 2 to 3. However, such behaviour is not universal, as there exist networks which admit a VLNC solution over a smaller set of characteristics of finite fields when the dimension is increased. Using the networks constructed in this paper, we further demonstrate that: (i) a network having an $m_{1}$ -dimensional VLNC solution over a finite field of some characteristic and an $m_{2}$ -dimensional VLNC solution over a finite field of some other characteristic may not have an $(m_{1} + m_{2})$ -dimensional VLNC solution over any finite field; (ii) there exist a class of networks for which scalar linear network coding (SLNC) over non-commutative rings has some advantage over SLNC over finite fields: the least sized non-commutative ring over which each network in the class has an SLNC solution is significantly lesser in size than the least sized finite field over which it has an SLNC solution. [ABSTRACT FROM AUTHOR]

This paper deals with two typical random number generation problems in information theory. One is the source resolvability problem (resolvability problem for short) and the other is the intrinsic randomness problem. In the literature, optimum achievable rates in these two problems with respect to the variational distance as well as the Kullback-Leibler (KL) divergence have already been analyzed. On the other hand, in this study we consider these two problems with respect to $f$ -divergences. The $f$ -divergence is a general non-negative measure between two probabilistic distributions on the basis of a convex function $f$. The class of $f$ -divergences includes several important measures such as the variational distance, the KL divergence, the Hellinger distance and so on. Hence, it is meaningful to consider the random number generation problems with respect to $f$ -divergences. In this paper, we impose some conditions on the function $f$ so as to simplify the analysis, that is, we consider a subclass of $f$ -divergences. Then, we first derive general formulas of the first-order optimum achievable rates with respect to $f$ -divergences. Next, we particularize our general formulas to several specified functions $f$. As a result, we reveal that it is easy to derive optimum achievable rates for several important measures from our general formulas. The second-order optimum achievable rates and optimistic optimum achievable rates have also been investigated. [ABSTRACT FROM AUTHOR]

In this paper, a family of $[{q}^{2}-1, 4, {q}^{2}-{q}-2]$ cyclic codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2}-1,{q}^{2}-5,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of cyclic codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Some of the subfield codes are optimal and some have the best known parameters. It is shown that the subfield codes are equivalent to a family of primitive BCH codes and thus the parameters of the BCH codes are solved. The duals of the subfield codes are also optimal with respect to the sphere-packing bound. A family of $[{q}^{2}, 4, {q}^{2}-{q}-1]$ linear codes over ${\mathbb F}_{{q}}$ meeting the Griesmer bound is presented. Their duals are $[{q}^{2},{q}^{2}-4,4]$ almost MDS codes and are optimal with respect to the sphere-packing bound. The ${q}_{0}$ -ary subfield codes of this family of linear codes are also investigated, where ${q}_{0}$ is any prime power such that q is power of ${q}_{0}$. Five infinite families of 2-designs are also constructed with three families of linear codes of this paper. [ABSTRACT FROM AUTHOR]

For a function $f$ from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{n}$ , the planarity of $f$ is usually measured by its differential uniformity and differential spectrum. In this paper, we propose the concept of vanishing flats, which supplies a combinatorial viewpoint on the planarity. First, the number of vanishing flats of $f$ can be regarded as a measure of the distance between $f$ and the set of almost perfect nonlinear functions. In some cases, the number of vanishing flats serves as an “intermediate” concept between differential uniformity and differential spectrum, which contains more information than differential uniformity, however less than the differential spectrum. Secondly, the set of vanishing flats forms a combinatorial configuration called partial quadruple system, since it conveys a detailed structural information about $f$. We initiate this study by considering the number of vanishing flats and the partial quadruple systems associated with monomials and Dembowski-Ostrom polynomials. In addition, we present an application of vanishing flats to the partition of a vector space into disjoint equidimensional affine spaces. We conclude the paper with several further questions and challenges. [ABSTRACT FROM AUTHOR]

The article lists the recipients of the 2014 Institute of Electrical and Electronics Engineers (IEEE) Communications Society and Information Theory Society Joint Paper Award including software developer Huseyin Simitci, electrical engineer Cheng Huang and researcher Parikshit Gopalan.

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented. [ABSTRACT FROM AUTHOR]

This paper explores the network simplification problem for Gaussian full-duplex relay networks with arbitrary topology. Particularly, given an $N$ -relay Gaussian full-duplex network, the network simplification problem seeks to find fundamental guarantees on the capacity of the best subnetwork, among a particular class of subnetworks, as a fraction of the full-network capacity. The focus of this work is the case when the selected subnetwork class is a path from the source to the destination. The main result of the paper shows that for an $N$ -relay Gaussian networks with arbitrary topology, the best route can in the worst case guarantee an approximate fraction $\frac {1}{ \lfloor N/2 \rfloor + 1}$ of the capacity of the full network, independently of the channel coefficients and/or operating SNR. Furthermore, this guarantee is shown to be fundamental, i.e., it is the highest worst-case guarantee that can be provided for routing in relay networks. A key step in the proof of the main result lies in the derivation of a simplification result for antenna selection in MIMO channels that may also be of independent interest. To the best of our knowledge, this is the first result that characterizes the performance of routing in comparison to physical layer cooperation techniques that approximately achieve the network capacity for general wireless network topologies. The results in this paper show that routing can, in the worst case, result in an unbounded gap from the network capacity - or reversely, physical layer cooperation can offer unbounded gains over routing. [ABSTRACT FROM AUTHOR]

Highly nonlinear functions (perfect nonlinear, maximum nonlinear, etc.) between finite fields have been studied in numerous papers. These concepts have been generalized first to finite abelian groups and then to finite nonabelian groups. In 2011, Poinsot and Pott introduced a new class of highly nonlinear functions between finite nonabelian groups, which are closely related to maximum nonlinear functions. They found such a function by a computer search, and proposed to find more such functions by theoretical constructions. Since then there is no progress in this topic. In this paper we continue the research in the direction proposed by Poinsot and Pott. Our purpose is to study the properties and constructions of this new class of highly nonlinear functions, called the absolute maximum nonlinear functions in this paper. In particular, for arbitrary finite (abelian or nonabelian) groups $K$ and $N$ with an absolute maximum nonlinear function $f: K \to N$ , we will prove that $N$ has to be abelian, and $f$ cannot be perfect nonlinear if $K$ is not abelian. Then we investigate the numerical constraints on the groups that have absolute maximum nonlinear functions. These constraints will eliminate the existence of absolute maximum nonlinear functions for many finite nonabelian groups. More importantly, using these constraints we will develop a method to construct absolute maximum nonlinear functions for some groups. In particular, we will determine all absolute maximum nonlinear functions on $A_4$ (the alternating group of degree 4). Furthermore, a general method to construct new absolute maximum nonlinear functions from the old ones will be given. [ABSTRACT FROM AUTHOR]

This paper considers the problem of secure parameter estimation when an estimation algorithm is prone to causative attacks. Causative attacks, in general, target decision-making algorithms (e.g., inference or learning algorithm) to alter their decisions in specific scenarios (e.g., distort parameter estimates for specific ranges of the parameter of interest). Such attacks influence the decisions via tampering with the mechanisms through which an algorithm acquires the statistical model of the population about which it aims to form a decision. Such attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the statistical model. In the presence of causative attacks, inference algorithms operate under a distorted statistical model for the data samples. This paper introduces a notion of secure parameter estimation and formalizes a framework under which secure estimation can be formulated and analyzed. The central premise underlying the secure estimation framework is that forming secure estimates introduces a new dimension to the estimation objective, pertaining to detecting attacks and isolating the true model. Since detection and isolation decisions themselves are imperfect, their inclusion induces an inherent coupling between the desired secure estimation objective and the auxiliary detection and isolation decisions that need to be formed in conjunction with the estimates. This paper establishes the fundamental interplay among these decisions, and characterizes the general decision rules in closed-forms for any desired estimation cost function. Furthermore, to circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm is provided, which is shown to enjoy certain optimality guarantees. Finally, the theory developed is applied to secure parameter estimation in sensor networks. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of secure communication in a wireline noiseless scenario where a source wishes to communicate to a number of destinations in the presence of a passive external adversary. Different from the multicast scenario, where all destinations are interested in receiving the same message, in this setting different destinations are interested in different messages. The main focus of this paper is on characterizing the secure capacity region, when the adversary has unbounded computational capabilities, but limited network presence. Towards this end, an outer bound on the secure capacity region is derived, and secure transmission schemes are designed and analyzed in terms of achieved rate performance. It is first shown that, for the case of two destinations, the designed scheme matches the outer bound, hence characterizing the secure capacity region. Then, a particular class of networks referred to as two-layer networks is considered, where the source communicates with the destinations by hopping information through one layer of relays. It is shown that the designed scheme is indeed capacity achieving for any two-layer network for which one of the following three conditions is satisfied: (i) the number of destinations is three, (ii) the number of edges eavesdropped by the adversary is one, (iii) the min-cut capacities assume specific values. It is also shown that two-layer networks can be used to model and study a more general class of networks, referred to as separable. The key feature of separable networks is that they can be partitioned into edge disjoint networks that satisfy specific min-cut properties. In particular, it is proved that the secure capacity region of any separable network can be characterized from the secure capacity region of the corresponding two-layer network. Finally, for an arbitrary network topology, a two-phase scheme is designed and its rate performance is compared with the capacity-achieving scheme for networks with two destinations. [ABSTRACT FROM AUTHOR]

In literatures, there are various constructions of frequency hopping sequence (FHS for short) sets with good Hamming correlations. Some papers employed only multiplicative groups of finite fields to construct FHS sets, while other papers implicitly used only additive groups of finite fields for construction of FHS sets. In this paper, we make use of both multiplicative and additive groups of finite fields simultaneously to present a construction of optimal FHS sets. The construction provides a new family of optimal $\left ({{q}^{{m}}-1,\frac {{q}^{{m}-{t}}-1}{{r}},{\it{ rq}}^{{t}};\frac {{q}^{{m}-{t}}-1}{{r}}+1}\right)$ frequency hopping sequence sets archiving the Peng-Fan bound. Thus, some FHS sets constructed in literatures using either multiplicative groups or additive groups of finite fields are included in our family. In addition, some other FHS sets can be obtained via the well-known recursive construction through one-coincidence sequence set. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

Coded computation techniques provide robustness against straggling workers in distributed computing. However, most of the existing schemes require exact provisioning of the straggling behavior and ignore the computations carried out by straggling workers. Moreover, these schemes are typically designed to recover the desired computation results accurately, while in many machine learning and iterative optimization algorithms, faster approximate solutions are known to result in an improvement in the overall convergence time. In this paper, we first introduce a novel coded matrix-vector multiplication scheme, called coded computation with partial recovery (CCPR), which benefits from the advantages of both coded and uncoded computation schemes, and reduces both the computation time and the decoding complexity by allowing a trade-off between the accuracy and the speed of computation. We then extend this approach to distributed implementation of more general computation tasks by proposing a coded communication scheme with partial recovery, where the results of subtasks computed by the workers are coded before being communicated. Numerical simulations on a large linear regression task confirm the benefits of the proposed scheme in terms of the trade-off between the computation accuracy and latency. [ABSTRACT FROM AUTHOR]

The researches of Golay complementary sequences (GCSs) over 16 and 64 quadrature amplitude modulation (QAM) from 2001 to 2008 were generalized to $4^{q} $ -QAM GCSs of length $2^{m}$ by Li (the generalized cases I-III for $q\ge 2$) in 2010 and Liu et al. (the generalized cases IV-V for $q\ge 3$) in 2013. Those sequences are presented by the combination of the quaternary standard GCSs and compatible offsets. By providing new compatible offsets based on the factorization of the integer $q$ , we propose two new constructions of $4^{q} $ -QAM GCSs, which have the generalized cases I-V as special cases. The numbers of the proposed GCSs are equal to the product of the number of the quaternary standard GCSs and the number of the compatible offsets. Denote the number of prime factors of $q$ counted with multiplicity by $\Omega (q)$. The number of new offsets in our first construction is lower bounded by a polynomial of $m$ with degree $\Omega (q)$ , while the numbers of offsets in the generalized cases I-III and IV-V are a linear polynomial and a quadratic polynomial of $m$ , respectively. If $q$ has a prime factor larger than 2, the number of new offsets in our second construction is lower bounded by a polynomial of $m$ with degree $\Omega (q)+1$. As an example, the new offsets in our two constructions for $q=6$ , whose number is bounded by a cubic polynomial, is also given. The proof in this paper implies that all the mentioned GCSs over QAM can be regarded as projections of Golay complementary arrays of size $2\times 2\times \cdots \times 2$. [ABSTRACT FROM AUTHOR]

We consider the $K$ -user Multiple Input Multiple Output (MIMO) Gaussian interference channel with $M$ antennas at each transmitter and $N$ antennas at each receiver. It is assumed that channel coefficients are constant real numbers and are available at all transmitters and at all receivers. The main objective of this paper is to characterize the number of Degrees of Freedom (DoF) of this channel. Using the real interference alignment technique introduced in Motahari et al., 2014, we show that $\frac {MN}{M+N} K$ degrees of freedom can be achieved for almost all channel realizations. Also, a new upper-bound on the DoF of this channel is provided. This upper-bound coincides with our achievable DoF for $K\geq K_{u} \triangleq \frac {M+N}{\gcd (M,N)}$ , where $\gcd (M,N)$ denotes the greatest common divisor of $M$ and $N$. This gives an exact characterization of DoF for $M\times N$ MIMO Gaussian interference channel in the case of $K\geq K_{u}$. Since there is no cooperation between transmit (or receive) antennas of each user in our transmission scheme, this result shows that the DoF benefit of joint processing in collocated antennas vanishes when the number of users is greater than a certain threshold. [ABSTRACT FROM AUTHOR]

We investigate the equilibrium behavior for the decentralized cheap talk problem for real random variables and quadratic cost criteria in which an encoder and a decoder have misaligned objective functions. In prior work, it has been shown that the number of bins in any equilibrium has to be countable, generalizing a classical result due to Crawford and Sobel who considered sources with density supported on [0, 1]. In this paper, we first refine this result in the context of log-concave sources. For sources with two-sided unbounded support, we prove that, for any finite number of bins, there exists a unique equilibrium. In contrast, for sources with semi-unbounded support, there may be a finite upper bound on the number of bins in equilibrium depending on certain conditions stated explicitly. Moreover, we prove that for log-concave sources, the expected costs of the encoder and the decoder in equilibrium decrease as the number of bins increases. Furthermore, for strictly log-concave sources with two-sided unbounded support, we prove convergence to the unique equilibrium under best response dynamics which starts with a given number of bins, making a connection with the classical theory of optimal quantization and convergence results of Lloyd’s method. In addition, we consider more general sources which satisfy certain assumptions on the tail(s) of the distribution and we show that there exist equilibria with infinitely many bins for sources with two-sided unbounded support. Further explicit characterizations are provided for sources with exponential, Gaussian, and compactly-supported probability distributions. [ABSTRACT FROM AUTHOR]

A new family of codes, called clustering-correcting codes, is presented in this paper. This family of codes is motivated by the special structure of the data that is stored in DNA-based storage systems. The data stored in these systems has the form of unordered sequences, also called strands, and every strand is synthesized thousands to millions of times, where some of these copies are read back during sequencing. Due to the unordered structure of the strands, an important task in the decoding process is to place them in their correct order. This is usually accomplished by allocating part of the strand for an index. However, in the presence of errors in the index field, important information on the order of the strands may be lost. Clustering-correcting codes ensure that if the distance between the index fields of two strands is small, their data fields have large distance. It is shown how this property enables to place the strands together in their correct clusters even in the presence of errors. We present lower and upper bounds on the size of clustering-correcting codes and an explicit construction of these codes which uses only a single symbol of redundancy. The results are first presented for the Hamming metric and are then extended for the edit distance. [ABSTRACT FROM AUTHOR]

Just as rank-metric or Gabidulin codes may be used to construct rate–diversity tradeoff optimal space–time codes, a recently introduced generalization for the sum-rank metric—linearized Reed–Solomon codes—accomplishes the same in the case of multiple fading blocks. In this paper, we provide the first explicit construction of minimal delay rate–diversity optimal multiblock space–time codes as an application of linearized Reed–Solomon codes. We also provide sequential decoders for these codes and, more generally, space–time codes constructed from finite field codes. Simulation results show that the proposed codes can outperform full diversity codes based on cyclic division algebras at low SNRs as well as utilize significantly smaller constellations. [ABSTRACT FROM AUTHOR]

A general class of Bayesian lower bounds when the underlying loss function is a Bregman divergence is demonstrated. This class can be considered as an extension of the Weinstein–Weiss family of bounds for the mean squared error and relies on finding a variational characterization of Bayesian risk. This approach allows for the derivation of a version of the Cramér–Rao bound that is specific to a given Bregman divergence. This new generalization of the Cramér–Rao bound reduces to the classical one when the loss function is taken to be the Euclidean norm. In order to evaluate the effectiveness of the new lower bounds, the paper also develops upper bounds on Bayesian risk, which are based on optimal linear estimators. The effectiveness of the new bound is evaluated in the Poisson noise setting. [ABSTRACT FROM AUTHOR]

In blind compression of quantum states, a sender Alice is given a specimen of a quantum state $\rho $ drawn from a known ensemble (but without knowing what $\rho $ is), and she transmits sufficient quantum data to a receiver Bob so that he can decode a near perfect specimen of $\rho $. For many such states drawn iid from the ensemble, the asymptotically achievable rate is the number of qubits required to be transmitted per state. The Holevo information is a lower bound for the achievable rate, and is attained for pure state ensembles, or in the related scenario of entanglement-assisted visible compression of mixed states wherein Alice knows what state is drawn. In this paper, we prove a general and robust lower bound on the achievable rate for ensembles of classical states, which holds even in the least demanding setting when Alice and Bob share free entanglement and a constant per-copy error is allowed. We apply the bound to a specific ensemble of only two states and prove a near-maximal separation (saturating the dimension bound in leading order) between the best achievable rate and the Holevo information for constant error. This also implies that the ensemble is incompressible – compression does not reduce the communication cost by much. Since the states are classical, the observed incompressibility is not fundamentally quantum mechanical. We lower bound the difference between the achievable rate and the Holevo information in terms of quantitative limitations to clone the specimen or to distinguish the two classical states. [ABSTRACT FROM AUTHOR]

In contrast to time series, graphical data is data indexed by the vertices and edges of a graph. Modern applications such as the internet, social networks, genomics and proteomics generate graphical data, often at large scale. The large scale argues for the need to compress such data for storage and subsequent processing. Since this data might have several components available in different locations, it is also important to study distributed compression of graphical data. In this paper, we derive a rate region for this problem which is a counterpart of the Slepian–Wolf theorem. We characterize the rate region when the statistical description of the distributed graphical data can be modeled as being one of two types – as a member of a sequence of marked sparse Erdős–Rényi ensembles or as a member of a sequence of marked configuration model ensembles. Our results are in terms of a generalization of the notion of entropy introduced by Bordenave and Caputo in the study of local weak limits of sparse graphs. Furthermore, we give a generalization of this result for Erdős–Rényi and configuration model ensembles with more than two sources. [ABSTRACT FROM AUTHOR]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

Local pseudorandom generators are a class of fundamental cryptographic primitives having very broad applications in theoretical cryptography. Following Couteau et al.’s work at ASIACRYPT 2018, this paper further studies the concrete security of one important class of local pseudorandom generators, i.e., Goldreich’s pseudorandom generators. Our first attack is of the guess-and-determine type. Our result significantly improves the state-of-the-art algorithm proposed by Couteau et al., in terms of both asymptotic and concrete complexity, and breaks all the challenge parameters they proposed. For instance, for a parameter set suggested for 128 bits of security, we could solve the instance faster by a factor of about 277, thereby destroying the claimed security completely. Our second attack further exploits the extremely sparse structure of the predicate $P_{5}$ and combines ideas from iterative decoding. This novel attack, named guess-and-decode, substantially improves the guess-and-determine approaches for cryptographic-relevant parameters. All the challenge parameter sets proposed in Couteau et al.’s work in ASIACRYPT 2018 aiming for 80-bit (128-bit) security levels can be solved in about 258 (278) operations. We suggest new parameters for achieving 80-bit (128-bit) security with respect to our attacks. We also extend the attacks to other promising predicates and investigate their resistance. [ABSTRACT FROM AUTHOR]

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, our argument establishes the optimality of Gaussian codebooks and hence, a closed-form formula for the optimal rate region. The second problem is Wyner’s common information and a generalization thereof, where conditional independence is generalized to a limit on the conditional mutual information. We present full explicit solutions for the scalar as well as the vector case. [ABSTRACT FROM AUTHOR]

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some $t$ -intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed. [ABSTRACT FROM AUTHOR]

This paper employs auxiliary receivers as a mathematical tool to identify Gallager-type auxiliary random variables and write outer bounds for some basic multiuser settings. This approach is then applied to the relay, interference, and broadcast channel settings, yielding new outer bounds that improve on existing outer bounds and strictly outperform classical outer bounds. For instance, we strictly improve on: the cutset outer bound for the scalar Gaussian relay channel, the outer bounds for the Gaussian Z-interference channel, and the outer bounds for the two receiver broadcast channel. [ABSTRACT FROM AUTHOR]

Distributed computing enables parallel execution of smaller tasks that make up a large computing job. Its purpose is to reduce the job completion time. However, random fluctuations in task service times lead to straggling tasks with long execution times. Redundancy provides diversity that allows job completion when only a subset of redundant tasks is executed, thus removing the dependency on the straggling tasks. Under constrained resources (here, a fixed number of parallel servers), increasing redundancy reduces the available resources for parallelism. In this paper, we characterize the diversity vs. parallelism trade-off and identify the optimal strategy among replication, coding, and splitting, which minimizes the expected job completion time. We consider three common service time distributions and establish three models that describe the scaling of these distributions with the task size. We find that different distributions with different scaling models operate optimally at different redundancy levels, thus requiring very different code rates. [ABSTRACT FROM AUTHOR]

For a continuous-time additive white Gaussian noise (AWGN) channel with possible feedback, it has been shown that as sampling gets infinitesimally fine, the mutual information of the associative discrete-time channels converges to that of the original continuous-time channel. We give in this paper more quantitative strengthenings of this result, which, among other implications, characterize how over-sampling approaches the true mutual information of a continuous-time Gaussian channel with bandwidth limit. The assumptions in our results are relatively mild. In particular, for the non-feedback case, compared to the Shannon-Nyquist sampling theorem, a widely used tool to connect continuous-time Gaussian channels to their discrete-time counterparts that requires the band-limitedness of the channel input, our results only require some integrability conditions on the power spectral density function of the input. [ABSTRACT FROM AUTHOR]

A functional PIR array code is a coding scheme which encodes some $s$ information bits into a $t\times m$ array such that every linear combination of the $s$ information bits has $k$ mutually disjoint recovering sets. Every recovering set consists of some of the array’s columns while it is allowed to read at most $\ell $ encoded bits from every column in order to receive the requested linear combination of the information bits. Functional batch array codes impose a stronger property where every multiset request of $k$ linear combinations has $k$ mutually disjoint recovering sets. Locality functional array codes demand that the size of every recovering set is restrained to be at most $r$. Given the values of $s, k, t, \ell,r$ , the goal of this paper is to study the optimal value of the number of columns $m$ such that these codes exist. Several lower bounds are presented as well as explicit constructions for several of these parameters. [ABSTRACT FROM AUTHOR]

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, log-determinants, and saturated coverage functions and see that they all have mathematically intuitive and practically useful expressions. Finally, we also study generalized independence between subsets of datapoints (random variables in the entropic case), and connect the independence characterizations to independence in log-submodular distributions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy preserving summarization—and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning. We perform real world as well as synthetic experiments on various data summarization tasks. [ABSTRACT FROM AUTHOR]

Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing a good resistance are known since 2008, but their output is a little too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. In the present paper, we introduce a generalization of the HWB functions into a construction of $n$ -variable balanced functions $f$ from $(n-1)$ -variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals constant 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters. We analyze the constructed functions $f$ , we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers. [ABSTRACT FROM AUTHOR]

Network localization is capable of providing accurate and ubiquitous position information for numerous wireless applications. This paper studies the accuracy of cooperative network localization in large-scale wireless networks. Based on a decomposition of the equivalent Fisher information matrix (EFIM), we develop a random-walk-inspired approach for the analysis of EFIM, and propose a position information routing interpretation of cooperative network localization. Using this approach, we show that in large lattice and stochastic geometric networks, when anchors are uniformly distributed, the average localization error of agents grows logarithmically with the reciprocal of anchor density in an asymptotic regime. The results are further illustrated using numerical examples. [ABSTRACT FROM AUTHOR]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

Due to its high data density and longevity, DNA is considered a promising medium for satisfying ever-increasing data storage needs. However, the diversity of errors that occur in DNA sequences makes efficient error-correction a challenging task. This paper aims to address simultaneously correcting two types of errors, namely, short tandem duplication and edit errors, where an edit error may be a substitution, deletion, or insertion. We focus on tandem repeats of length at most 3 and design codes for correcting an arbitrary number of duplication errors and one edit error. Because an edited symbol can be duplicated many times (as part of substrings of various lengths), a single edit can affect an unbounded substring of the retrieved word. However, we show that with appropriate preprocessing, the effect may be limited to a substring of finite length, thus making efficient error-correction possible. We construct a code for correcting the aforementioned errors and provide lower bounds for its rate. Compared to optimal codes correcting only duplication errors, numerical results show that the asymptotic cost of protecting against an additional edit is only 0.003 bits/symbol when the alphabet has size 4, an important case corresponding to data storage in DNA. [ABSTRACT FROM AUTHOR]

As a special subclass of cyclic codes, BCH codes have wide applications in communication and storage systems. A BCH code of length $n$ over $\mathbb {F}_{q}$ is always relative to an $n$ -th primitive root of unity $\beta $ in an extension field of $\mathbb {F}_{q}$ , and is called a dually-BCH code if its dual is also a BCH code relative to the same $\beta $. The question as to whether a BCH code is a dually-BCH code is in general very hard to answer. In this paper, an answer to this question for primitive narrow-sense BCH codes and projective narrow-sense ternary BCH codes is given. Sufficient and necessary conditions in terms of the designed distances $\delta $ will be presented to ensure that these BCH codes are dually-BCH codes. In addition, the parameters of the primitive narrow-sense BCH codes and their dual codes are investigated. Some lower bounds on minimum distances of the dual codes of primitive and projective narrow-sense BCH codes are developed. Especially for binary primitive narrow-sense BCH codes, the new bounds on the minimum distances of the dual codes improve the classical Sidel’nikov bound, and are also better than the Carlitz and Uchiyama bound for large designed distances $\delta $. The question as to what subclasses of cyclic codes are BCH codes is also answered to some extent. As a byproduct, the parameters of some subclasses of cyclic codes are also investigated. [ABSTRACT FROM AUTHOR]

Minimal linear codes are in one-to-one correspondence with special types of blocking sets of projective spaces over a finite field, which are called strong or cutting blocking sets. Minimal linear codes have been studied since decades but their tight connection with cutting blocking sets of finite projective spaces was unfolded only in the past few years, and it has not been fully exploited yet. In this paper we apply finite geometric and probabilistic arguments to contribute to the field of minimal codes. We prove an upper bound on the minimal length of minimal codes of dimension $k$ over the $q$ -element Galois field which is linear in both $q$ and $k$ , hence improve the previous superlinear bounds. This result determines the minimal length up to a small constant factor. We also improve the lower and upper bounds on the size of so called higgledy-piggledy line sets in projective spaces and apply these results to present improved bounds on the size of covering codes and saturating sets in projective spaces as well. [ABSTRACT FROM AUTHOR]

The Binary Iterative Hard Thresholding (BIHT) algorithm is a popular reconstruction method for one-bit compressed sensing due to its simplicity and fast empirical convergence. Despite considerable research on this algorithm, a theoretical understanding of the corresponding approximation error and convergence rate still remains an open problem. This paper shows that the normalized version of BIHT (NBIHT) achieves an approximation error rate optimal up to logarithmic factors. More precisely, using $m$ one-bit measurements of an $s$ -sparse vector $x$ , we prove that the approximation error of NBIHT is of order $O \left ({\frac{1 }{ m }}\right)$ up to logarithmic factors, which matches the information-theoretic lower bound $\Omega \left ({\frac{1 }{ m }}\right)$ proved by Jacques, Laska, Boufounos, and Baraniuk in 2013. To our knowledge, this is the first theoretical analysis of a BIHT-type algorithm that explains the optimal rate of error decay empirically observed in the literature. This also makes NBIHT the first provable computationally-efficient one-bit compressed sensing algorithm that breaks the inverse square-root error decay rate $O \left ({\frac{1 }{ m^{1/2} }}\right)\vphantom {{\left ({\frac{1 }{ m^{1/2} }}\right)}^{'}}$. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks, where a source node communicates to a destination node through a multi-hop path of $N$ relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD $N$ -relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the $N+1$ listen/transmit states (out of the $2^{N}$ possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed. [ABSTRACT FROM AUTHOR]

This paper considers multiplexing two sequences of messages with two different decoding delays over a packet erasure channel. In each time slot, the source constructs a packet based on the current and previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. The destination must perfectly recover every source message in the first sequence subject to a decoding delay ${T}_{\mathrm{ v}}$ and every source message in the second sequence subject to a shorter decoding delay ${T}_{\mathrm{ u}}\le {T}_{\mathrm{ v}}$. We assume that the channel loss model introduces a burst erasure of a fixed length B on the discrete timeline. Under this channel loss assumption, the capacity region for the case where ${T}_{\mathrm{ v}}\le {T}_{\mathrm{ u}}+{B}$ was previously solved. In this paper, we fully characterize the capacity region for the remaining case ${T}_{\mathrm{ v}}> {T}_{\mathrm{ u}}+{B}$. The key step in the achievability proof is achieving the non-trivial corner point of the capacity region through using a multiplexed streaming code constructed by superimposing two single-stream codes. The main idea in the converse proof is obtaining a genie-aided bound when the channel is subject to a periodic erasure pattern where each period consists of a length-B burst erasure followed by a length- ${T}_{\mathrm{ u}}$ noiseless duration. [ABSTRACT FROM AUTHOR]

In this paper, we study the vector Gaussian Chief Executive Officer (CEO) problem under logarithmic loss distortion measure. Specifically, ${K} \geq 2$ agents observe independently corrupted Gaussian noisy versions of a remote vector Gaussian source, and communicate independently with a decoder or CEO over rate-constrained noise-free links. The CEO also has its own Gaussian noisy observation of the source and wants to reconstruct the remote source to within some prescribed distortion level where the incurred distortion is measured under the logarithmic loss penalty criterion. We find an explicit characterization of the rate-distortion region of this model. The result can be seen as the counterpart to the vector Gaussian setting of that by Courtade-Weissman which provides the rate-distortion region of the model in the discrete memoryless setting. For the proof of this result, we obtain an outer bound by means of a technique that relies on the de Bruijn identity and the properties of Fisher information. The approach is similar to Ekrem-Ulukus outer bounding technique for the vector Gaussian CEO problem under quadratic distortion measure, for which it was there found generally non-tight; but it is shown here to yield a complete characterization of the region for the case of logarithmic loss measure. Also, we show that Gaussian test channels with time-sharing exhaust the Berger-Tung inner bound, which is optimal. Furthermore, application of our results allows us to find the complete solutions of two related problems: a quadratic vector Gaussian CEO problem with determinant constraint and the vector Gaussian distributed Information Bottleneck problem. Finally, we develop Blahut-Arimoto type algorithms that allow to compute numerically the regions provided in this paper, for both discrete and Gaussian models. With the known relevance of the logarithmic loss fidelity measure in the context of learning and prediction, the proposed algorithms may find usefulness in a variety of applications where learning is performed distributively. We illustrate the efficiency of our algorithms through some numerical examples. [ABSTRACT FROM AUTHOR]

The tight lower bound on the redundancy of optimal prefix-free codes in terms of a given symbol probability (not necessarily the largest or the smallest one) has been derived in the literature. The first goal of this paper is to derive the tight lower bounds in terms of $j$ ($j>1$) known symbol probabilities of the source using some properties of Kullback-Leibler distance. Since fix-free codes are special prefix-free codes (for which no codeword is a suffix of the other codewords), it is clear that all lower bounds on the redundancy of optimal prefix-free codes are also valid for fix-free ones. Accordingly, the second question of the paper is on the tightness of the derived lower bounds for optimal fix-free codes. It is proven that these lower bounds are tight for optimal fix-free codes if $j\leq 3$ , and are not tight for $j\geq 4$. Also, it is shown that the tight lower bound in terms of the probability of the most likely symbol is the same for optimal prefix-free and optimal fix-free codes. [ABSTRACT FROM AUTHOR]