Volume 55, Nº 2 (2019)

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 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 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.