We derive a lower bound on the secrecy capacity of a compound wiretap channel with channel state information at the transmitter which matches the general upper bound on the secrecy capacity of general compound wiretap channels given by Liang et al. [1], thus establishing a full coding theorem in this case. We achieve this with a stronger secrecy criterion and the maximum error probability criterion, and with a decoder that is robust against the effect of randomization in the encoding. This relieves us from the need of decoding the randomization parameter, which is in general impossible within this model. Moreover, we prove a lower bound on the secrecy capacity of a compound wiretap channel without channel state information and derive a multiletter expression for the capacity in this communication scenario.

We consider a family of energy-constrained diamond norms on the set of Hermitian- preserving linear maps (superoperators) between Banach spaces of trace class operators. We prove that any norm from this family generates strong (pointwise) convergence on the set of all quantum channels (which is more adequate for describing variations of infinite-dimensional channels than the diamond norm topology). We obtain continuity bounds for information characteristics (in particular, classical capacities) of energy-constrained infinite-dimensional quantum channels (as functions of a channel) with respect to the energy-constrained diamond norms, which imply uniform continuity of these characteristics with respect to the strong convergence topology.

The impact of diversity on reliable communication over arbitrarily varying channels (AVC) is investigated as follows. First, the concept of an identical state-constrained jammer is motivated. Second, it is proved that symmetrizability of binary symmetric AVCs (AVBSC) caused by identical state-constrained jamming is circumvented when communication takes place over at least three orthogonal channels. Third, it is proved that the deterministic capacity of the identical state-constrained AVBSC is continuous and shows super-activation. This effect was hitherto demonstrated only for quantum communication and for classical communication under secrecy constraints.

We use Hamilton equations to identify most likely scenarios of long queues being formed in ergodic Jackson networks. Since the associated Hamiltonians are discontinuous and piecewise Lipschitz, one has to invoke methods of nonsmooth analysis. Time reversal of the Hamilton equations yields fluid equations for the dual network. Accordingly, the optimal trajectories are time reversals of the fluid trajectories of the dual network. Those trajectories are shown to belong to domains that satisfy a certain condition of being “essential.” As an illustration, we consider a two-station Jackson network. In addition, we prove certain properties of substochastic matrices, which may be of interest in their own right.

We introduce a new wide class of error-correcting codes, called non-split toric codes. These codes are a natural generalization of toric codes where non-split algebraic tori are taken instead of usual (i.e., split) ones. The main advantage of the new codes is their cyclicity; hence, they can possibly be decoded quite fast. Many classical codes, such as (doubly-extended) Reed-Solomon and (projective) Reed-Muller codes, are contained (up to equivalence) in the new class. Our codes are explicitly described in terms of algebraic and toric geometries over finite fields; therefore, they can easily be constructed in practice. Finally, we obtain new cyclic reversible codes, namely non-split toric codes on the del Pezzo surface of degree 6 and Picard number 1. We also compute their parameters, which prove to attain current lower bounds at least for small finite fields.

The operation of Minkowski addition of geometric figures has a discrete analog, addition of subsets of a Boolean cube viewed as a vector space over the two-element field. Subsets of the Boolean cube (or multivariable Boolean functions) form a monoid with respect to this operation. This monoid is of interest in classical discrete analysis as well as in a number of problems related to information theory. We consider several complexity aspects of this monoid, namely structural, algorithmic, and algebraic.

We prove equivalence of using the modulus metric and Euclidean metric in solving the soft decoding problem for a memoryless discrete channel with binary input and Q-ary output. For such a channel, we give an example of a construction of binary codes correcting t binary errors in the Hamming metric. The constructed codes correct errors at the output of a demodulator with Q quantization errors as (t + 1)(Q − 1) − 1 errors in the modulus metric. The obtained codes are shown to have polynomial decoding complexity.

We substantially improve a presently known explicit exponentially growing lower bound on the chromatic number of a Euclidean space with forbidden equilateral triangle. Furthermore, we improve an exponentially growing lower bound on the chromatic number of distance graphs with large girth. These refinements are obtained by improving known upper bounds on the product of cardinalities of two families of homogeneous subsets with one forbidden cross-intersection.

This work is a survey on completely regular codes. Known properties, relations with other combinatorial structures, and construction methods are considered. The existence problem is also discussed, and known results for some particular cases are established. In addition, we present several new results on completely regular codes with covering radius ρ = 2 and on extended completely regular codes.

This paper considers a multimessage network where each node may send a message to any other node in the network. Under the discrete memoryless model, we prove the strong converse theorem for any network whose cut-set bound is tight, i.e., achievable. Our result implies that for any fixed rate vector that resides outside the capacity region, the average error probability of any sequence of length-n codes operated at the rate vector must tend to 1 as n approaches infinity. The proof is based on the method of types and is inspired by the work of Csiszár and Körner in 1982 which fully characterized the reliability function of any discrete memoryless channel with feedback for rates above capacity. In addition, we generalize the strong converse theorem to the Gaussian model where each node is subject to an almost-sure power constraint. Important consequences of our results are new strong converses for the Gaussian multiple access channel with feedback and the following relay channels under both models: the degraded relay channel (RC), the RC with orthogonal sender components, and the general RC with feedback.

An exact expression for the probability of inversion of a large spin is established in the form of an asymptotic expansion in the series of Bessel functions with orders belonging to an arithmetic progression. Based on the new asymptotic expansion, a formula for the inversion time of the spin is derived.

We consider the problem of determining extreme values of the Rényi entropy for a discrete random variable provided that the value of the α-coupling for this random variable and another one with a given probability distribution is fixed.

We develop refinements of the Levenshtein bound in q-ary Hamming spaces by taking into account the discrete nature of the distances versus the continuous behavior of certain parameters used by Levenshtein. We investigate the first relevant cases and present new bounds. In particular, we derive generalizations and q-ary analogs of the MacEliece bound. Furthermore, we provide evidence that our approach is as good as the complete linear programming and discuss how faster are our calculations. Finally, we present a table with parameters of codes which, if exist, would attain our bounds.

We consider the problem of estimating the noise level σ 2 in a Gaussian linear model Y = Xβ+σξ, where ξ ∈ ℝ n is a standard discrete white Gaussian noise and β ∈ ℝ p an unknown nuisance vector. It is assumed that X is a known ill-conditioned n × p matrix with n ≥ p and with large dimension p. In this situation the vector β is estimated with the help of spectral regularization of the maximum likelihood estimate, and the noise level estimate is computed with the help of adaptive (i.e., data-driven) normalization of the quadratic prediction error. For this estimate, we compute its concentration rate around the pseudo-estimate ||Y − Xβ||2/n.

We study chromatic numbers of spaces $$\mathbb{R}_p^n=(\mathbb{R}^n, \ell_p)$$ R p n = ( R n , ℓ p ) with forbidden monochromatic sets. For some sets, we for the first time obtain explicit exponentially growing lower bounds for the corresponding chromatic numbers; for some others, we substantially improve previously known bounds.

We introduce a construction of a set of code sequences {C n (m) : n ≥ 1, m ≥ 1} with memory order m and code length N(n). {C n (m)} is a generalization of polar codes presented by Arıkan in [1], where the encoder mapping with length N(n) is obtained recursively from the encoder mappings with lengths N(n − 1) and N(n − m), and {C n (m)} coincides with the original polar codes when m = 1. We show that {C n (m)} achieves the symmetric capacity I(W) of an arbitrary binary-input, discrete-output memoryless channel W for any fixed m. We also obtain an upper bound on the probability of block-decoding error P e of {C n (m)} and show that $${P_e} = O({2^{ - {N^\beta }}})$$ P e = O ( 2 − N β ) is achievable for β < 1/[1+m(ϕ − 1)], where ϕ ∈ (1, 2] is the largest real root of the polynomial F(m, ρ) = ρ m − ρ m − 1 − 1. The encoding and decoding complexities of {C n (m)} decrease with increasing m, which proves the existence of new polar coding schemes that have lower complexity than Arıkan’s construction.

We show that converting an n-digit number from a binary to Fibonacci representation and backward can be realized by Boolean circuits of complexity O(M(n) log n), where M(n) is the complexity of integer multiplication. For a more general case of r-Fibonacci representations, the obtained complexity estimates are of the form $${2^O}{(\sqrt {\log n} )_n}$$ 2 O ( log n ) n .

We propose a new version of the proof of Good's theorem stating that the Kronecker power of an arbitrary square matrix can be represented as a matrix power of a sparse matrix Z. We propose new variants of sparse matrices Z. We observe that for another version of the tensor power of a matrix, the b-power, there exists an analog of another Good's expansion but no analog of this theorem.

We consider recurrence sequences over the set of integers with generating functions being arbitrary superpositions of polynomial functions and the sg function, called polynomial recurrence sequences. We define polynomial-register (PR) machines, close to random-access machines. We prove that computations on PR machines can be modeled by polynomial recurrence sequences. On the other hand, computation of elements of a polynomial recurrence sequence can be implemented using a suitable PR machine.

The common wisdom is that the capacity of parallel channels is usually additive. This was also conjectured by Shannon for the zero-error capacity function, which was later disproved by constructing explicit counterexamples demonstrating the zero-error capacity to be super-additive. Despite these explicit examples for the zero-error capacity, there is surprisingly little known for nontrivial channels. This paper addresses this question for the arbitrarily varying channel (AVC) under list decoding by developing a complete theory. The list capacity function is studied and shown to be discontinuous, and the corresponding discontinuity points are characterized for all possible list sizes. For parallel AVCs it is then shown that the list capacity is super-additive, implying that joint encoding and decoding for two parallel AVCs can yield a larger list capacity than independent processing of both channels. This discrepancy is shown to be arbitrarily large. Furthermore, the developed theory is applied to the arbitrarily varying wiretap channel to address the scenario of secure communication over AVCs.