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.

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.

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 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 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 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 consider the problem of determining the maximum and minimum of the Rényi divergence D λ(P||Q) and D λ(Q||P) for two probability distribution P and Q of discrete random variables X and Y provided that the probability distribution P and the parameter α of α-coupling between X and Y are fixed, i.e., provided that Pr{X = Y } = α.

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.

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.

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.

The paper considers a continuous-time birth–death process where the jump rate has an asymptotically polynomial dependence on the process position. We obtain a rough exponential asymptotic for the probability of trajectories of a re-scaled process contained within a neighborhood of a given continuous nonnegative function.

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.

We establish the strong Poisson hypothesis for symmetric closed networks. In particular, we prove asymptotic independence of nodes as the size of the system tends to infinity.

We study the asymptotic behavior of probabilities of first-order properties for random uniform hypergraphs. In 1990, J. Spencer introduced the notion of a spectrum for graph properties and proved the existence of a first-order property with an infinite spectrum. In this paper we give a definition of a spectrum for properties of uniform hypergraphs and establish an almost tight bound for the minimum quantifier depth of a first-order formula with infinite spectrum.

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs.

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 propose a test to distinguish between two classes of distribution tails using only higher order statistics of a sample and prove its consistency. We do not assume the corresponding distribution functions to belong to any maximum domain of attraction.

For q-ary Hamming spaces we address the problem of the minimum number of points such that any point of the space is uniquely determined by its (Hamming) distances to them. It is conjectured that for a fixed q and growing dimension n of the Hamming space this number asymptotically behaves as 2n/ log q n. We prove this conjecture for q = 3 and q = 4; for q = 2 its validity has been known for half a century.

Quantum entanglement can be used in a communication scheme to establish a correlation between successive channel inputs that is impossible by classical means. It is known that the classical capacity of quantum channels can be enhanced by such entangled encoding schemes, but this is not always the case. In this paper, we prove that a strong converse theorem holds for the classical capacity of an entanglement-breaking channel even when it is assisted by a classical feedback link from the receiver to the transmitter. In doing so, we identify a bound on the strong converse exponent, which determines the exponentially decaying rate at which the success probability tends to zero, for a sequence of codes with communication rate exceeding capacity. Proving a strong converse, along with an achievability theorem, shows that the classical capacity is a sharp boundary between reliable and unreliable communication regimes. One of the main tools in our proof is the sandwiched Rényi relative entropy. The same method of proof is used to derive an exponential bound on the success probability when communicating over an arbitrary quantum channel assisted by classical feedback, provided that the transmitter does not use entangled encoding schemes.