A binary code is said to be a disjunctive (s, ℓ) cover-free code if it is an incidence matrix of a family of sets where the intersection of any ℓ sets is not covered by the union of any other s sets of this family. A binary code is said to be a list-decoding disjunctive of strength s with list size L if it is an incidence matrix of a family of sets where the union of any s sets can cover no more that L − 1 other sets of this family. For L = ℓ = 1, both definitions coincide, and the corresponding binary code is called a disjunctive s-code. This paper is aimed at improving previously known and obtaining new bounds on the rate of these codes. The most interesting of the new results is a lower bound on the rate of disjunctive (s, ℓ) cover-free codes obtained by random coding over the ensemble of binary constant-weight codes; its ratio to the best known upper bound converges as s → ∞, with an arbitrary fixed ℓ ≥ 1, to the limit 2e −2 = 0.271 ... In the classical case of ℓ = 1, this means that the upper bound on the rate of disjunctive s-codes constructed in 1982 by D’yachkov and Rykov is asymptotically attained up to a constant factor a, 2e −2 ≤ a ≤ 1.

We study some structural properties of Construction-A lattices obtained from low density parity check codes over prime fields. Such lattices are called low density Construction-A (LDA) lattices, and permit low-complexity belief propagation decoding for transmission over Gaussian channels. It has been shown that LDA lattices achieve the capacity of the power constrained additive white Gaussian noise (AWGN) channel with closest lattice-point decoding, and simulations suggested that they perform well under belief propagation decoding. We continue this line of work and prove that these lattices are good for packing and mean squared error quantization and that their duals are good for packing. With this, we can conclude that codes constructed using nested LDA lattices can achieve the capacity of the power constrained AWGN channel, the capacity of the dirty paper channel, the rates guaranteed by the computeand-forward protocol, and the best known rates for bidirectional relaying with perfect secrecy.

This paper strengthens the interpretation and understanding of the classical capacity of the pure-loss bosonic channel, first established in [1]. In particular, we first prove that there exists a trade-off between communication rate and error probability if one imposes only a mean photon number constraint on the channel inputs. That is, if we demand that the mean number of photons at the channel input cannot be any larger than some positive number NS, then it is possible to respect this constraint with a code that operates at a rate g(ηNS/(1-p)) where p is the code error probability, η is the channel transmissivity, and g(x) is the entropy of a bosonic thermal state with mean photon number x. Then we prove that a strong converse theorem holds for the classical capacity of this channel (that such a rate-error trade-off cannot occur) if one instead demands for a maximum photon number constraint, in such a way that mostly all of the “shadow” of the average density operator for a given code is required to be on a subspace with photon number no larger than nNS, so that the shadow outside this subspace vanishes as the number n of channel uses becomes large. Finally, we prove that a small modification of the well-known coherent-state coding scheme meets this more demanding constraint.

We give a detailed description of a low-dimensional quantum channel (input dimension 4, Choi rank 3) demonstrating the symmetric form of superactivation of one-shot quantum zero-error capacity. This property means appearance of a noiseless (perfectly reversible) subchannel in the tensor square of a channel having no noiseless subchannels. Then we describe a quantum channel with an arbitrary given level of symmetric superactivation (including the infinite value). We also show that superactivation of one-shot quantum zero-error capacity of a channel can be reformulated in terms of quantum measurement theory as appearance of an indistinguishable subspace for the tensor product of two observables having no indistinguishable subspaces.

In the projective plane PG(2, q), we consider an iterative construction of complete arcs which adds a new point in each step. It is proved that uncovered points are uniformly distributed over the plane. For more than half of steps of the iterative process, we prove an estimate for the number of newly covered points in every step. A natural (and well-founded) conjecture is made that the estimate holds for the other steps too. As a result, we obtain upper bounds on the smallest size t 2(2, q) of a complete arc in PG(2, q), in particular, $$\begin{array}{*{20}c} {t_2 (2,q) < \sqrt q \sqrt {3\ln q + \ln \ln q + \ln 3} + \sqrt {\frac{q} {{3\ln q}}} + 3,} \\ {t_2 (2,q) < 1.87\sqrt {q\ln q} .} \\ \end{array}$$ Nonstandard types of upper bounds on t 2(2, q) are considered, one of them being new. The effectiveness of the new bounds is illustrated by comparing them with the smallest known sizes of complete arcs obtained in recent works of the authors and in the present paper via computer search in a wide region of q. We note a connection of the considered problems with the so-called birthday problem (or birthday paradox).

A novel soft-decision decoding algorithm for Reed-Solomon codes over GF(2 m ) is proposed, which is based on representing them as polar codes with dynamic frozen symbols and applying the successive cancellation method. A further performance improvement is obtained by exploiting multiple permutations of codewords which are taken from the automorphism group of Reed-Muller codes. It is also shown that the proposed algorithm can be simplified in the case of decoding a binary image of the Reed-Solomon code.

For information transmission, a discrete-time channel with independent additive Gaussian noise is used. There is also another channel with independent additive Gaussian noise (the feedback channel), and the transmitter observes all outputs of the forward channel without delay via that channel. Transmission of nonexponentially many messages is considered (i.e., the transmission rate is zero), and the achievable decoding error exponent for such a combination of channels is investigated. The transmission method strengthens the method previously used by the authors for the BSC and Gaussian channels. In particular, for small feedback noise, this yields a gain of 33.3% (instead of 23.6% earlier in the similar case of a Gaussian channel).

The problem of determining both the maximum and minimum entropy of a random variable Y as well as the maximum absolute value of the difference between entropies of Y and another random variable X is considered under the condition that the probability distribution of X is fixed and the error probability (i.e., the probability of noncoincidence of random values of X and Y) is given. A precise expression for the minimum entropy of Y is found. Some conditions under which the entropy of Y takes its maximum value are pointed out. In other cases, some lower and upper bounds are obtained for the maximum entropy of Y as well as for the maximum absolute value of the difference between entropies of Y and X.

We prove results on sharp asymptotics of probabilities $$P\left\{ {\int\limits_0^1 {\left| {X(t)} \right|^p dt < \varepsilon ^p } } \right\}, \varepsilon \to 0,$$ where 0 < p < ∞, for three Gaussian processes X(t), namely the stationary and nonstationary Ornstein-Uhlenbeck process and the Bogoliubov process. The analysis is based on the Laplace method for sojourn times of a Wiener process.

This paper deals with transportation polytopes in the probability simplex (i.e., sets of categorical bivariate probability distributions with prescribed marginals). Information projections between such polytopes are studied, and a sufficient condition is described under which these mappings are homeomorphisms.

In this paper we prove the Ahlswede-Khachatrian conjecture [1] up to a finite number of cases, which can be checked using modern computers. This conjecture implies the conjecture from [2] and the Manickam-Miklós-Singhi conjecture.

All different Steiner systems S(2 m , 4, 3) of order 2 m and rank 2 m − m − 1 + s over $$\mathbb{F}_2$$ , where 0 ≤ s ≤ m − 1, are constructed. The number of different systems S(2 m , 4, 3) whose incident matrices are orthogonal to a fixed code is obtained. A connection between the number of different Steiner systems and of different Latin cubes is described.

DNA sequences are sequences with elements from the quaternary DNA alphabet {A, C, G, T}. An important property of them is their directedness and ability to form duplexes as a result of hybridization process, i.e., coalescing two oppositely directed sequences. In biological experiments exploiting this property it is necessary to generate an ensemble of such sequences (DNA codes) consisting of pairs of DNA sequences referred to as Watson-Crick duplexes. Furthermore, for any two words of the DNA code that do not form a Watson-Crick duplex, hybridization energy—stability measure of a potential DNA duplex—is upper bounded by a constant specified by conditions of an experiment. This problem can naturally be interpreted in terms of coding theory. Continuing our previous works, we consider a nonadditive similarity function for two DNA sequences, which most adequately models their hybridization energy. For the maximum cardinality of DNA codes based on this similarity, we establish a Singleton upper bound and present an example of an optimal construction. Using ensembles of DNA codes with special constraints on codewords, which we call Fibonacci ensembles, we obtain a random-coding lower bound on the maximum cardinality of DNA codes under this similarity function.

We study 1-factorizations of a complete graph with n vertices. The lower bound on the number of such factorizations is refined. A new proof of the upper bound is given.

We prove results on sharp asymptotics of probabilities p{integral X-1 vertical bar(0)(t)vertical bar(p) dt 0 where 0 < p < infinity, for three Gaussian processes X(t), namely the stationary and nonstationary Ornstein-Uhlenbeck process and the Bogoliubov process. The analysis is based on the Laplace method for sojourn times of a Wiener process.

We study functional consequences of the interlacing property consisting in that a new configuration of “particles” occurs in gaps between elements of a previous configuration. This property was introduced by I.M. Gelfand in terms of spectra of sequences of matrices of increasing dimensions and turned out to be highly needed in many areas of modern mathematics. We examine conditions under which the next generation is “on average smoother” than the previous one and discuss issues related to “complexity” of the set of pairs of interlacing functions.

We investigate the capacity of the Q-frequency S-user vector adder channel (channel with intensity information) introduced by Chang and Wolf. Both coordinated and uncoordinated types of transmission are considered. Asymptotic (under the conditions Q → ∞, S = γQ, 0 < γ < ∞) upper and lower bounds on the relative (per subchannel) capacity are derived. The lower bound for the coordinated case is shown to increase with γ. At the same time, the relative capacity for the uncoordinated case is upper bounded by a constant.

Often, for a source to be encoded it is only known (or assumed) that its model belongs to some known family; parameters of models are unknown. The number of context Markov models in a family can be enormous, and methods for finding the best of them to describe a current block (message fragment of length n) have not been discussed previously. We propose a way to solve this problem and describe a coding algorithm.

We prove two correlation inequalities conjectured in [1] for functions that are linear combinations of unimodal Boolean monotone nondecreasing functions.