Search

The article provides information on the periodical "Institute of Electrical and Electronics Engineers (IEEE) Transactions on Information Theory," including emphasis of the publication on the transmission, processing and utilization of information, abstract requirements for the submitted paper, and the copyright policy of the IEEE.

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

The article offers information on the recipients of the 2007 IEEE Information Theory Society Paper Award. Hanan Weingarten has masteral and doctorate degrees in electrical engineering from the Technion-Israel Institute of Technology. Yossef Steinberg was a Lady Davis Fellow in the Department of Electrical Engineering and held visiting appointments in the Department of Electrical Engineering at Princeton University in New Jersey. Shlomo Shamai has research interests which encompasses a wide spectrum of topics in information theory and statistical communications.

In wireless networks, the link connectivity may be intermittent due to shadowing, burstiness of data arrival, or uncoordinated resource allocation. In this paper, we model the intermittence of links as Bernoulli distributed random channel states, termed intermittence channel states, and study the impact of the corresponding channel state information at the transmitter (CSIT) in a two-user Gaussian broadcast channel (BC). Moreover, due to the heterogeneous timeliness of intermittence channel states, the CSIT considered in this paper is hybrid. More specifically, the CSIT of each link can be perfectly (causally or non-causally) available, delayed, or not available. When the links are connected, we adopt a general setting that the received signal-to-noise ratios can be different. Our contribution is the characterization of the capacity regions of intermittent Gaussian BC to within bounded gaps for all combinations of hybrid CSIT, except for scenario DN (delayed CSIT of receiver 1, no CSIT of receiver 2). For scenario DN, we propose an opportunistic physical layer network coding scheme that achieves a strictly larger degree-of-freedom (DoF) region than the no-CSIT DoF region. As a corollary, single-user CSIT is able to increase the sum DoF for intermittent Gaussian BC (also the capacity region for the erasure BC, as a by-product). This result is in sharp contrast to the recent negative result by Davoodi and Jafar, where it is shown that for fast-fading multiple-input single-output BC with continuous channel states, single-user CSIT does not help at all in terms of sum DoF. [ABSTRACT FROM AUTHOR]

In an interesting paper, Prof. C. Ding provided three constructions of cyclic codes of length being a product of two primes. Numerical data shows that many codes from these constructions are best cyclic codes of the same length and dimension over the same finite field. However, not much is known about these codes. In this paper, we explain some of the numerical data by developing a general method on cyclic codes of composite length and on estimating the minimum distance. We also provide a general construction of cyclic codes of composite length which are related to Ding’s constructions. Numerical data shows that it produces many best cyclic codes as well. Finally, we point out how these cyclic codes can be used to construct convolutional codes with large free distance. [ABSTRACT FROM AUTHOR]

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov–Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions. [ABSTRACT FROM AUTHOR]

This paper provides upper and lower bounds on the optimal guessing moments of a random variable taking values on a finite set when side information may be available. These moments quantify the number of guesses required for correctly identifying the unknown object and, similarly to Arikan’s bounds, they are expressed in terms of the Arimoto-Rényi conditional entropy. Although Arikan’s bounds are asymptotically tight, the improvement of the bounds in this paper is significant in the non-asymptotic regime. Relationships between moments of the optimal guessing function and the MAP error probability are also established, characterizing the exact locus of their attainable values. The bounds on optimal guessing moments serve to improve non-asymptotic bounds on the cumulant generating function of the codeword lengths for fixed-to-variable optimal lossless source coding without prefix constraints. Non-asymptotic bounds on the reliability function of discrete memoryless sources are derived as well. Relying on these techniques, lower bounds on the cumulant generating function of the codeword lengths are derived, by means of the smooth Rényi entropy, for source codes that allow decoding errors. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of learning undirected graphical models from data generated according to the Glauber dynamics (also known as the Gibbs sampler). The Glauber dynamics is a Markov chain that sequentially updates individual nodes (variables) in a graphical model and it is frequently used to sample from the stationary distribution (to which it converges given sufficient time). Additionally, the Glauber dynamics is a natural dynamical model in a variety of settings. This paper deviates from the standard formulation of graphical model learning in the literature, where one assumes access to independent identically distributed samples from the distribution. Much of the research on graphical model learning has been directed toward finding algorithms with low computational cost. As the main result of this paper, we establish that the problem of reconstructing binary pairwise graphical models is computationally tractable when we observe the Glauber dynamics. Specifically, we show that a binary pairwise graphical model on p nodes with maximum degree d can be learned in time f(d)p^2\log p , for a function f(d) defined explicitly in this paper, using nearly the information-theoretic minimum number of samples. [ABSTRACT FROM AUTHOR]

Let m be an even positive integer. A Boolean bent function ƒ on F2m-1 × F2 is called a cyclic bent function if for any a ≠ b ∈ F2m-1 and ε ∈ F2, ƒ(ax1, x2)+ ƒ(bx1, x2 + ε) is always bent, where x1 ∈ F2m-1, x2 ∈ F2. Cyclic bent functions look extremely rare. This paper focuses on cyclic bent functions on F2m-1 × F2 and their applications. The first objective of this paper is to establish a link between quadratic cyclic bent functions and a special type of prequasifields, and construct a class of quadratic cyclic bent functions from the Kantor-Williams prequasifields. The second objective is to use cyclic bent functions to construct families of optimal sequences. The results of this paper show that cyclic bent functions have nice applications in several fields such as coding theory, symmetric cryptography, and CDMA communication. [ABSTRACT FROM AUTHOR]

The article presents information for authors interested submitting their manuscripts to be included in the "IEEE Transactions on Information Theory" journal, including the scope and limitations of the theoretical and experimental papers, the format for each paper and the Open Researcher and Contributor Identification (ORCID) requirement.

A common method for reading information stored in DNA molecules is shotgun sequencing. This method outputs a histogram of the frequencies of all the molecules’ substrings of a given length $\ell $. To protect against noisy readings, the rank-modulation scheme encodes the information in the relative ranking of the substring frequencies, instead of their absolute values. However, the best rank-modulation codes for shotgun sequencing have low rates which are asymptotically vanishing. In this paper we propose new constructions of rank-modulation codes for shotgun sequencing. The first code construction is systematic, allowing the user to arbitrarily set the frequencies of a large subset of the substrings, which the encoder then completes to a permutation that may be realized by a DNA molecule. The construction is then improved by allowing the user to set the frequencies of additional substrings, at the cost of imposing constraints on the frequencies. The resulting codes have higher, non-vanishing rates, compared with previously known codes. As an example, for histograms of substrings of length $\ell =2$ , and an alphabet of size 4 (as in DNA molecules), we are able to construct a code with rate $\approx 0.909$ , whereas previously, the best construction resulted in a code with rate $\approx 0.654$. Additionally, the encoded information in our construction may be written to shorter DNA molecules than possible before. We also prove that the systematic codes constructed in this paper are the largest possible among all systematic codes. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

The Bose-Chaudhuri-Hocquenghem (BCH) codes are a well-studied subclass of cyclic codes that have found numerous applications in error correction and notably in quantum information processing. They are widely used in data storage and communication systems. A subclass of attractive BCH codes is the narrow-sense BCH codes over the Galois field ${\mathrm {GF}}(q)$ with length $q+1$ , which are closely related to the action of the projective general linear group of degree two on the projective line. Despite its interest, not much is known about this class of BCH codes. This paper aims to study some of the codes within this class and specifically narrow-sense antiprimitive BCH codes (these codes are also linear complementary duals (LCD) codes that have interesting practical recent applications in cryptography, among other benefits). We shall use tools and combine arguments from algebraic coding theory, combinatorial designs, and group theory (group actions, representation theory of finite groups, etc.) to investigate narrow-sense antiprimitive BCH Codes and extend results from the recent literature. Notably, the dimension, the minimum distance of some $q$ -ary BCH codes with length $q+1$ , and their duals are determined in this paper. The dual codes of the narrow-sense antiprimitive BCH codes derived in this paper include almost MDS codes. Furthermore, the classification of ${\mathrm {PGL}}(2, p^{m})$ -invariant codes over ${\mathrm {GF}}(p^{h})$ is completed. As an application of this result, the $p$ -ranks of all incidence structures invariant under the projective general linear group ${\mathrm {PGL}}(2, p^{m})$ are determined. Furthermore, infinite families of narrow-sense BCH codes admitting a 3-transitive automorphism group are obtained. Via these BCH codes, a coding-theory approach to constructing the Witt spherical geometry designs is presented. The BCH codes proposed in this paper are good candidates for permutation decoding, as they have a relatively large group of automorphisms. [ABSTRACT FROM AUTHOR]

The article discusses about theoretical and experimental papers concerned with the transmission, processing, and utilization of information.

Reed-Solomon (RS) codes are widely used in distributed storage systems. In this paper, we study the repair bandwidth and sub-packetization size of RS codes. The repair bandwidth is defined as the amount of transmitted information from surviving nodes to a failed node. The RS code can be viewed as a polynomial over a finite field $GF(q^\ell)$ evaluated at a set of points, where $\ell $ is called the sub-packetization size. Smaller bandwidth reduces the network traffic in distributed storage, and smaller $\ell $ facilitates the implementation of RS codes with lower complexity. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire finite field. While the sub-packetization size can be arbitrarily small, the repair bandwidth is higher than the minimum storage regenerating (MSR) bound. Tamo, Ye, and Barg achieved the MSR bound but the sub-packetization size grows faster than the exponential function of the number of the evaluation points. In this paper, we present code constructions and repair schemes that extend these results to accommodate different sizes of the evaluation points. In other words, we design schemes that provide points in between. These schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we generalize our schemes to manage multiple failures. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over $\mathbb {F}_{q}$ exists. This problem is completely solved for the case where $q$ is even. For $q$ is odd, some $q$ -ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of $q$ -ary MDS Euclidean self-dual codes by using generalized Reed–Solomon (GRS for short) codes and extended GRS codes. [ABSTRACT FROM AUTHOR]

In this paper, a general framework of constructing the optimal frequency-hopping sequence (FHS) sets is presented based on the designated direct product. Under this framework, we obtain infinitely many new optimal FHS sets by combining some one-coincide (OC) sequence sets that are newly constructed in this paper with some known optimal FHS sets. Our constructions are also based on extension method. However, our constructions give new and flexible parameters due to the free choice of OC sequence set. As a result, our constructions allow a great flexibility of choosing parameters of FHS sets for a given frequency-hopping spread spectrum system. [ABSTRACT FROM AUTHOR]

In fog-aided cellular systems, content delivery latency can be minimized by jointly optimizing edge caching and transmission strategies. In order to account for the cache capacity limitations at the edge nodes (ENs), transmission generally involves both fronthaul transfer from a cloud processor with access to the content library to the ENs and wireless delivery from the ENs to the users. In this paper, the resulting problem is studied from an information-theoretic viewpoint by making the following practically relevant assumptions: 1) the ENs have multiple antennas; 2) only uncoded fractional caching is allowed; 3) the fronthaul links are used to send fractions of contents; and 4) the ENs are constrained to use one-shot linear zero-forcing precoding on the wireless channel. Assuming off-line proactive caching and focusing on a high signal-to-noise ratio (SNR) latency metric, the optimal information-theoretic performance is investigated under both serial and pipelined fronthaul-edge transmission modes. The analysis characterizes the minimum high-SNR latency in terms of normalized delivery time (NDT) for worst case users’ demands. The characterization is exact for a subset of system parameters and is generally optimal within a multiplicative factor of 3/2 for the serial case and 2 for the pipelined case. The results bring insights into the optimal interplay between edge and cloud processing in fog-aided wireless networks as a function of system resources, including the number of antennas at the ENs, the ENs’ cache capacity, and the fronthaul capacity. [ABSTRACT FROM AUTHOR]

The main goal in group testing is to recover a small subset of defective items from a larger population while efficiently reducing the total number of (possibly noisy) required tests/measurements. Under the assumption that the input-output statistical relationship (i.e., channel law) is known to the recovery algorithm, the fundamental as well as the computational limits of the group testing problem are relatively better understood than when these statistical relationships are unknown. Practical considerations, however, render this assumption inapplicable, and “blind” recovery/estimation procedures, independent of the input-output statistics, are desired. In this paper, we analyze the fundamental limits of a general noisy group testing problem, when this relationship is unknown. Specifically, in the first part of this paper, we propose an efficient scheme, based on the idea of separate-decoding of items (where each item is recovered separately), for which we derive sufficient conditions on the number of tests required for exact recovery. The difficulty in obtaining these conditions stems from the fact that we allow the number of defective items to grow with the population size, which in turn requires delicate concentration analysis of certain probabilities. Furthermore, we show that in several scenarios, our proposed scheme achieves the same performance as that of the corresponding non-blind recovery algorithm (where the input-output statistics are known), implying that the proposed blind scheme is robust/universal. Finally, in the second part of this paper, we propose also an inefficient combinatorial-based scheme (or, “joint-decoding”), for which we derive similar sufficient conditions. [ABSTRACT FROM AUTHOR]

This paper considers secret-key generation between several agents and a base station that observe independent and identically distributed realizations of correlated random variables. Each agent wishes to generate the longest possible individual key with the base station by means of public communication. All keys must be jointly kept secret from all external entities. In this many-to-one secret-key generation setting, it can be shown that the agents can take advantage of a collective protocol to increase the sum rate of their generated keys. However, when each agent is only interested in maximizing its own secret-key rate, agents may be unwilling to participate in a collective protocol. Furthermore, when such a collective protocol is employed, how to fairly allocate individual key rates arises as a valid issue. This paper studies the tension between cooperation and self-interest with a game-theoretic treatment. This paper establishes that cooperation is in the best interest of all individualistic agents and that there exist individual secret-key rate allocations that incentivize the agents to follow the protocol. In addition, an explicit coding scheme that achieves such allocations is proposed. [ABSTRACT FROM AUTHOR]

In a paper by Guruswami et al., it was shown that the length $n$ of a $q$ -ary linear locally recoverable code with distance $d \geqslant 5$ is upper bounded by $O(dq^{3})$. Thus, it is a challenging problem to construct $q$ -ary locally recoverable codes with distance $d \geqslant 5$ and length approaching the upper bound. The same paper also gave an algorithmic construction of $q$ -ary locally recoverable codes with locality $r$ and length $n=\Omega _{r}(q^{2})$ for $d=5$ and 6, where $\Omega _{r}$ means that the implicit constant depends on locality $r$. In this paper, we present an explicit construction of $q$ -ary locally recoverable codes of distance $d= 5$ and 6 via binary constant weight codes. It turns out that 1) our construction is simpler and more explicit and 2) the length of our codes is greater than previously known. [ABSTRACT FROM AUTHOR]

This paper investigates the maximal secret communication rate over a wiretap channel subject to reliability and secrecy constraints at a given blocklength. New achievability and converse bounds are derived, which are uniformly tighter than existing bounds, and lead to the tightest bounds on the second-order coding rate for discrete memoryless and Gaussian wiretap channels. The exact second-order coding rate is established for semi-deterministic wiretap channels, which characterizes the optimal tradeoff between reliability and secrecy in the finite-blocklength regime. Underlying our achievability bounds are two new privacy amplification results, which not only refine the classic privacy amplification results, but also achieve secrecy under the stronger semantic-security metric. [ABSTRACT FROM AUTHOR]

This paper studies the capacity of an $n$ -dimensional vector Gaussian noise channel subject to the constraint that an input must lie in the ball of radius $R$ centered at the origin. It is known that in this setting, the optimizing input distribution is supported on a finite number of concentric spheres. However, the number, the positions, and the probabilities of the spheres are generally unknown. This paper characterizes necessary and sufficient conditions on the constraint $R$ , such that the input distribution supported on a single sphere is optimal. The maximum $\bar {R}_{n}$ , such that using only a single sphere is optimal, is shown to be a solution of an integral equation. Moreover, it is shown that $\bar {R}_{n}$ scales as $\sqrt {n}$ and the exact limit of $\frac {\bar {R}_{n}}{\sqrt {n}}$ is found. [ABSTRACT FROM AUTHOR]

Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate. [ABSTRACT FROM AUTHOR]

The repair problem in distributed storage addresses recovery of the data encoded using an erasure code, for instance, a Reed–Solomon (RS) code. We consider the problem of repairing a single node or multiple nodes in RS-coded storage systems using the smallest possible amount of inter-nodal communication. According to the cut-set bound, communication cost of repairing $h\geqslant 1$ failed nodes for an $(n,k=n-r)$ maximum distance separable (MDS) code using $d$ helper nodes is at least $dhl/(d+h-k)$ , where $l$ is the size of the node. Guruswami and Wootters (2016) initiated the study of efficient repair of RS codes, showing that they can be repaired using a smaller bandwidth than under the trivial approach. At the same time, their work as well as follow-up papers stopped short of constructing RS codes (or any scalar MDS codes) that meet the cut-set bound with equality. In this paper, we construct the families of RS codes that achieve the cut-set bound for repair of one or several nodes. In the single-node case, we present the RS codes of length $n$ over the field ${\mathbb F}_{q^{l}}, l=\exp ((1+o(1))n\log n)$ that meet the cut-set bound. We also prove an almost matching lower bound on $l$ , showing that super-exponential scaling is both necessary and sufficient for scalar MDS codes to achieve the cut-set bound using linear repair schemes. For the case of multiple nodes, we construct a family of RS codes that achieve the cut-set bound universally for the repair of any $h=1,2, {\dots },r$ failed nodes from any subset of $d$ helper nodes, $k\leqslant d\leqslant n-h$. For a fixed number of parities $r$ , the node size of the constructed codes is close to the smallest possible node size for codes with such properties. [ABSTRACT FROM AUTHOR]

In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper. [ABSTRACT FROM AUTHOR]

Consider observing a collection of discrete events within a network that reflect how network nodes influence one another. Such data are common in spike trains recorded from biological neural networks, interactions within a social network, and a variety of other settings. Data of this form may be modeled as self-exciting point processes, in which the likelihood of future events depends on the past events. This paper addresses the problem of estimating self-excitation parameters and inferring the underlying functional network structure from self-exciting point process data. Past work in this area was limited by strong assumptions which are addressed by the novel approach here. Specifically, in this paper we 1) incorporate saturation in a point process model which both ensures stability and models non-linear thresholding effects; 2) impose general low-dimensional structural assumptions that include sparsity, group sparsity, and low-rankness that allows bounds to be developed in the high-dimensional setting; and 3) incorporate long-range memory effects through moving average and higher-order auto-regressive components. Using our general framework, we provide a number of novel theoretical guarantees for high-dimensional self-exciting point processes that reflect the role played by the underlying network structure and long-term memory. We also provide simulations and real data examples to support our methodology and main results. [ABSTRACT FROM AUTHOR]

Constacyclic codes are well-known generalizations of cyclic and negacyclic codes. Due to their rich algebraic structure, constacyclic codes are used to construct quantum codes and symbol-pair codes. Let ${\mathbb {F}}_{q}$ be a finite field with order $q$ , where $q$ is a positive power of a prime $p$. Suppose that $n$ is a positive integer and the product of distinct prime factors of $n$ divides $q-1$ , i.e., $rad(n)\mid (q-1)$. In this paper, we explicitly factorize the polynomial $x^{n}-\lambda $ for each $\lambda \in {\mathbb {F}}_{q}^{*}$. As applications, first, we obtain all repeated-root $\lambda $ -constacyclic codes and their dual codes of length $np^{s}$ over ${\mathbb {F}}_{q}$ ; second, we determine all simple-root LCD cyclic codes and LCD negacyclic codes of length $n$ over ${\mathbb {F}}_{q}$ ; third, we list all self-dual repeated-root negacyclic codes of length $np^{s}$ over ${\mathbb {F}}_{q}$. In contrast to known results, the lengths of constacyclic codes in this paper have more flexible parameters. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

This paper aims to develop the insights into Bayesian truth serum (BTS) mechanism by postulating a sequence of seven natural conditions reminiscent of axioms in information theory. The condition that reduces a larger family of mechanisms to BTS is additivity, akin to the axiomatic development of entropy. The seven conditions identify BTS as the unique scoring rule for ranking respondents in situations in which respondents are asked to choose an alternative from a finite set and provide predictions of their peers’ propensities to choose, for finite or infinite sets of respondents. [ABSTRACT FROM AUTHOR]

In many different applications, it is important to determine the Hilbert transform of a given function. However, it is generally impossible to calculate it in closed form. Therefore Hilbert transform approximations are used. This paper studies the convergence and divergence behavior of general classes of such approximation methods. These classes are characterized by two very natural axioms and they include basically all known traditional numerical algorithms. The convergence of these methods is investigated on a family of signal spaces of continuous functions with finite energy. These spaces are parametrized by a number which measures the energy concentration in the low frequency components of the signal. It is shown that stable methods only exist on signal spaces with a sufficient energy concentration and this paper gives some explicit examples of convergent methods. On all other spaces in the family of signal spaces, every sampling-based Hilbert transform approximation shows a blowup behavior of its peak value, i.e., on these spaces, every sampling-based Hilbert transform approximation diverges. [ABSTRACT FROM AUTHOR]

This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute–forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute–forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute–forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from $K$ senders. [ABSTRACT FROM AUTHOR]

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed–Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp–Massey type. Fourth, decoding interleaved Reed–Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp–Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt–Sidorenko–Bossert bound and the Roth–Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms. [ABSTRACT FROM AUTHOR]

This paper studies a two-user state-dependent Gaussian multiple-access channel (MAC) with state noncausally known at one encoder. Two scenarios are considered: 1) each user wishes to communicate an independent message to the common receiver; and 2) the two encoders send a common message to the receiver and the non-cognitive encoder (i.e., the encoder that does not know the state) sends an independent individual message (this model is also known as the MAC with degraded message sets). For both scenarios, new outer bounds on the capacity region are derived, which improve uniformly over the best known outer bounds. In the first scenario, the two corner points of the capacity region as well as the sum rate capacity are established, and it is shown that a single-letter solution is adequate to achieve both the corner points and the sum rate capacity. Furthermore, the full capacity region is characterized in situations in which the sum rate capacity is equal to the capacity of the helper problem. The proof exploits the optimal-transportation idea of Polyanskiy and Wu (which was used previously to establish an outer bound on the capacity region of the interference channel) and the worst case Gaussian noise result for the case in which the input and the noise are dependent. [ABSTRACT FROM AUTHOR]

Algebraic topology studies topological spaces with the help of tools from abstract algebra. The main focus of this paper is to show that many concepts from algebraic topology can be conveniently expressed in terms of (normal) factor graphs. As an application, we give an alternative proof of a classical duality result of Kramers and Wannier, which expresses the partition function of the 2-D Ising model at a low temperature in terms of the partition function of the 2-D Ising model at a high temperature. Moreover, we discuss analogous results for the 3-D Ising model and the Potts model. [ABSTRACT FROM AUTHOR]

This paper considers structure learning from data with $n$ samples of $p$ variables, assuming that the structure is a forest, using the Chow–Liu algorithm. Specifically, for incomplete data, we construct two model selection algorithms that complete in $O(p^{2})$ steps: one obtains a forest with the maximum posterior probability given the data and the other obtains a forest that converges to the true one as $n$ increases. We show that the two forests are generally different when some values are missing. In addition, we present estimations for benchmark data sets to demonstrate that both algorithms work in realistic situations. Moreover, we derive the conditional entropy provided that no value is missing, and we evaluate the per-sample expected redundancy for the universal coding of incomplete data in terms of the number of non-missing samples. [ABSTRACT FROM AUTHOR]

Approximate message passing (AMP) refers to a class of efficient algorithms for statistical estimation in high-dimensional problems such as compressed sensing and low-rank matrix estimation. This paper analyzes the performance of AMP in the regime where the problem dimension is large but finite. For concreteness, we consider the setting of high-dimensional regression, where the goal is to estimate a high-dimensional vector $\beta _{0}$ from a noisy measurement $y=A \beta _{0} + w$. AMP is a low-complexity, scalable algorithm for this problem. Under suitable assumptions on the measurement matrix $A$ , AMP has the attractive feature that its performance can be accurately characterized in the large system limit by a simple scalar iteration called state evolution. Previous proofs of the validity of state evolution have all been asymptotic convergence results. In this paper, we derive a concentration inequality for AMP with Gaussian matrices with independent and identically distributed (i.i.d.) entries and finite dimension $n \times N$. The result shows that the probability of deviation from the state evolution prediction falls exponentially in $n$. This provides theoretical support for empirical findings that have demonstrated excellent agreement of AMP performance with state evolution predictions for moderately large dimensions. The concentration inequality also indicates that the number of AMP iterations $t$ can grow no faster than order $({\log n}/{\log \log n})$ for the performance to be close to the state evolution predictions with high probability. The analysis can be extended to obtain similar non-asymptotic results for AMP in other settings such as low-rank matrix estimation. [ABSTRACT FROM AUTHOR]

The zero-error capacity of a channel is defined as the maximum rate at which it is possible to transmit information with zero probability of error. In this paper, we settle all previously unsolved cases for the zero-error capacity of binary channels with one memory. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

These instructions give guidelines for preparing papers for this publication. Presents information for authors publishing in this journal. [ABSTRACT FROM AUTHOR]

The article offers information on preparation of manuscripts, graphical abstract, and open access related to the periodical.

In a recent paper [1], Rini et al. proved a capacity result for the discrete memoryless cognitive interference channel, under the condition named “better cognitive decoding.” We show that this capacity region is the same as the capacity region characterized by Wu et al. in [2]. [ABSTRACT FROM PUBLISHER]

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]

This paper considers a massive random access problem in which a large number of sporadically active devices wish to communicate with a base station (BS) equipped with massive multiple-input multiple-output (MIMO) antennas. Each device is preassigned a unique signature sequence, and the BS identifies the active devices by detecting which sequences are transmitted. This device activity detection problem can be formulated as a maximum likelihood estimation (MLE) problem for which the sample covariance matrix of the received signal is a sufficient statistic. The goal of this paper is to characterize the feasible set of problem parameters under which this covariance based approach is able to successfully recover the device activities in the massive MIMO regime. Through an analysis of the asymptotic behaviors of MLE via its associated Fisher information matrix, this paper derives a necessary and sufficient condition on the Fisher information matrix to ensure a vanishing probability of detection error as the number of antennas goes to infinity, based on which a numerical phase transition analysis is obtained. This condition is also examined from a perspective of covariance matching, which relates the phase transition analysis to a recently derived scaling law. Further, we provide a characterization of the distribution of the estimation error in MLE, based on which the error probabilities in device activity detection can be accurately predicted. Finally, this paper studies a random access scheme with joint device activity and data detection and analyzes its performance in a similar way. [ABSTRACT FROM AUTHOR]

This paper formulates a distributed computation problem, where a master asks ${\mathsf N}$ distributed workers to compute a linearly separable function. The task function can be expressed as ${\mathsf K}_{\mathrm{ c}}$ linear combinations of ${\mathsf K}$ messages, where each message is a function of one dataset. Our objective is to find the optimal tradeoff between the computation cost (number of uncoded datasets assigned to each worker) and the communication cost (number of symbols the master must download), such that from the answers of any ${\mathsf N}_{\mathrm{ r}}$ out of ${\mathsf N}$ workers the master can recover the task function with high probability, where the coefficients of the ${\mathsf K}_{\mathrm{ c}}$ linear combinations are uniformly i.i.d. over some large enough finite field. The formulated problem can be seen as a generalized version of some existing problems, such as distributed gradient coding and distributed linear transform. In this paper, we consider the specific case where the computation cost is minimum, and propose novel achievability schemes and converse bounds for the optimal communication cost. Achievability and converse bounds coincide for some system parameters; when they do not match, we prove that the achievable distributed computing scheme is optimal under the constraint of a widely used ‘cyclic assignment’ scheme on the datasets. Our results also show that when ${\mathsf K}= {\mathsf N}$ , with the same communication cost as the optimal distributed gradient coding scheme proposed by Tandon et al. from which the master recovers one linear combination of ${\mathsf K}$ messages, our proposed scheme can let the master recover any additional ${\mathsf N}_{\mathrm{ r}}-1$ independent linear combinations of messages with high probability. [ABSTRACT FROM AUTHOR]

As an optimal combinatorial object, zero-difference balanced (ZDB) functions introduced by Ding in 2008, are a generalization of the well-known perfect nonlinear functions. ZDB functions have received much attention in recent years due to its important applications in coding theory and sequence design. One objective of this paper is to present a construction of ZDB functions based on a kind of generalized cyclotomy. It generates ZDB functions over cyclic group with new parameters which can not be produced by earlier constructions. Another objective of this paper is to employ these ZDB functions to obtain at the same time: 1) optimal constant-composition codes; 2) perfect difference systems of sets; and 3) optimal frequency-hopping sequences, all with new parameters. [ABSTRACT FROM PUBLISHER]

Volume estimates of metric balls in manifolds find diverse applications in information and coding theory. In this paper, new results for the volume of a metric ball in unitary group are derived via tools from random matrix theory. The first result is an integral representation of the exact volume, which involves a Toeplitz determinant of Bessel functions. A simple but accurate limiting volume formula is then obtained by invoking Szegő’s strong limit theorem for large Toeplitz matrices. The derived asymptotic volume formula enables analytical evaluation of some coding-theoretic bounds of unitary codes. In particular, the Gilbert–Varshamov lower bound and the Hamming upper bound on the cardinality as well as the resulting bounds on code rate and minimum distance are derived. Moreover, bounds on the scaling law of code rate are found. Finally, a closed-form bound on the diversity sum relevant to unitary space-time codes is obtained, which was only computed numerically in the literature. [ABSTRACT FROM AUTHOR]

This paper is about deriving lower bounds on the error exponents for the two-user interference channel under the random coding regime for several ensembles. Specifically, we first analyze the standard random coding ensemble, where the codebooks are comprised of independently and identically distributed (i.i.d.) codewords. For this ensemble, we focus on optimum decoding, which is in contrast to other, suboptimal decoding rules that have been used in the literature (e.g., joint typicality decoding, treating interference as noise, and so on). The fact that the interfering signal is a codeword, rather than an i.i.d. noise process, complicates the application of conventional techniques of performance analysis of the optimum decoder. In addition, unfortunately, these conventional techniques result in loose bounds. Using analytical tools rooted in statistical physics, as well as advanced union bounds, we derive single-letter formulas for the random coding error exponents. We compare our results with the best known lower bound on the error exponent, and show that our exponents can be strictly better. Then, in the second part of this paper, we consider more complicated coding ensembles and find a lower bound on the error exponent associated with the celebrated Han–Kobayashi random coding ensemble, which is based on superposition coding. [ABSTRACT FROM AUTHOR]