Two partial orderings among communication channels, namely “being degradable into” and “being less noisy than,” are reconsidered in the light of recent results about statistical comparisons of quantum channels. Though our analysis covers at once both classical and quantum channels, we also provide a separate treatment of classical noisy channels and show how in this case an alternative self-contained proof can be constructed, with its own particular merits with respect to the general result.

The Doob graph D(m, n), where m > 0, is a Cartesian product of m copies of the Shrikhande graph and n copies of the complete graph K 4 on four vertices. The Doob graph D(m, n) is a distance-regular graph with the same parameters as the Hamming graph H(2m + n, 4). We give a characterization of MDS codes in Doob graphs D(m, n) with code distance at least 3. Up to equivalence, there are m 3/36+7m 2/24+11m/12+1−(m mod 2)/8−(m mod 3)/9 MDS codes with code distance 2m + n in D(m, n), two codes with distance 3 in each of D(2, 0) and D(2, 1) and with distance 4 in D(2, 1), and one code with distance 3 in each of D(1, 2) and D(1, 3) and with distance 4 in each of D(1, 3) and D(2, 2).

We say that an s-subset of codewords of a binary code X is s L -bad in X if there exists an L-subset of other codewords in X whose disjunctive sum is covered by the disjunctive sum of the given s codewords. Otherwise, this s-subset of codewords is said to be s L -good in X. A binary code X is said to be a list-decoding disjunctive code of strength s and list size L (an s L -LD code) if it does not contain s L -bad subsets of codewords. We consider a probabilistic generalization of s L -LD codes; namely, we say that a code X is an almost disjunctive s L -LD code if the fraction of s L -good subsets of codewords in X is close to 1. Using the random coding method on the ensemble of binary constant-weight codes, we establish lower bounds on the capacity and error exponent of almost disjunctive s L -LD codes. For this ensemble, the obtained lower bounds are tight and show that the capacity of almost disjunctive s L -LD codes is greater than the zero-error capacity of disjunctive s L -LD codes.

An increasing number of applications is concerned with recovering a sparse matrix from noisy observations. In this paper, we consider the setting where each row of an unknown matrix is sparse. We establish minimax optimal rates of convergence for estimating matrices with row sparsity. A major focus in the present paper is on the derivation of lower bounds.

We propose a modification of the addition law on the Edwards curve over a prime field. We prove three theorems on properties of coordinates of high-order points and on a degenerate pair of twisted curves. We propose an algorithm for reconstructing all unknown points kP of the Edwards curve when only 1/8 of the points are known.

We study a family of distance graphs in ℝ n . We present bounds for independence numbers which are asymptotically tight as n → ∞. We substantially improve upper bounds on chromatic numbers of these graphs, and in a number of cases we give explicit constructions of independence sets.

We address the problem of error correction by linear block codes under the assumption that the syndrome of a received vector is found with errors. We propose a construction of parity-check matrices which allow to solve the syndrome equation even with an erroneous syndrome, in particular, parity-check matrices with minimum redundancy, which are analogs of Reed-Solomon codes for this problem. We also establish analogs of classical coding theory bounds, namely the Hamming, Singleton, and Gilbert-Varshamov bounds. We show that the new problem can be considered as a generalization of the well-known Ulam’s problem on searching with a lie and as a discrete analog of the compressed sensing problem.

We investigate binary orthogonal arrays by making use of the fact that all possible distance distributions of the arrays under investigation and of related arrays can be computed. We apply certain relations for reducing the number of feasible distance distributions. In some cases this leads to nonexistence results. In particular, we prove that there exist no binary orthogonal arrays with parameters (strength, length, cardinality) = (4, 10, 6 · 24), (4, 11, 6 · 24), (4, 12, 7 · 24), (5, 11, 6 · 25), (5, 12, 6 · 25), and (5, 13, 7 · 25).

We consider two-hop multipath routing in wireless networks. Errors occurring in transmission through different paths can be correlated. We explicitly find eigenvectors and eigenvalues of the transition probability matrix describing the system. We obtain an expression for the delivery probability of a packet to a final destination.

In this paper we analyze approximation of stable linear time-invariant systems, like the Hilbert transform, by sampling series for bandlimited functions in the Paley–Wiener space PW π 1 . It is known that there exist systems and functions such that the approximation process is weakly divergent, i.e., divergent for certain subsequences. Here we strengthen this result by proving strong divergence, i.e., divergence for all subsequences. Further, in case of divergence, we give the divergence speed. We consider sampling at Nyquist rate as well as oversampling with adaptive choice of the kernel. Finally, connections between strong divergence and the Banach–Steinhaus theorem, which is not powerful enough to prove strong divergence, are discussed.

The well-known approach of Bose, Ray-Chaudhuri, and Hocquenghem and its generalization by Hartmann and Tzeng are lower bounds on the minimum Hamming distance of simple-root cyclic codes. We generalize these two bounds to the case of repeated-root cyclic codes and present a syndrome-based burst error decoding algorithm with guaranteed decoding radius based on an associated folded cyclic code. Furthermore, we present a third technique for bounding the minimum Hamming distance based on the embedding of a given repeated-root cyclic code into a repeated-root cyclic product code. A second quadratic-time probabilistic burst error decoding procedure based on the third bound is outlined.

Let X and Y be discrete random variables having probability distributions P X and P Y , respectively. A necessary and sufficient condition is obtained for the existence of an α-coupling of these random variables, i.e., for the existence of their joint distribution such that Pr{X = Y} = α, where α, 0 ≤ α ≤ 1, is a given constant. This problem is closely related with the problem of determining the minima of the divergences D(P Z ‖ P X ) and D(P X ‖ P Z ) over all probability distributions P Z of a random variable Z given P X and under the condition that Pr{Z = X} = α. An explicit solution for this problem is also obtained.

The Vernam cipher, or one-time pad, plays an important role in cryptography because it is perfectly secure. In this cipher a key is a sequence of equiprobable independently generated symbols. We show that under small disturbance of these properties the obtained cipher is close to the Vernam cipher in the case where the enciphered plaintext and the key are generated by stationary ergodic sources.

We consider a data protection scheme where error-correcting codes can be used for efficient protection against unauthorized copying organized by coalitions of cardinality c ∈ N of malicious users. We find limits of range of the parameters of prospective q-ary Reed–Muller codes for which these codes are c-TA and c-FP codes for copyright protection.

We present a new method for fast approximation of zeta constants, i.e., values ζ(n) of the Riemann zeta function, n ≥ 2, n is an integer, by rational fractions. The method makes it possible to fast approximate zeta constants and certain combinations of successive values of zeta constants by rational fractions. By choosing values of coefficients involved in the combinations, one can control the convergence rate of the approximations and the computation complexity for the zeta constants.

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.

We prove that values of an arbitrary eigenfunction of a q-ary n-dimensional hypercube can be uniquely reconstructed at all vertices inside a ball if its values on the corresponding sphere are known; we give sufficient conditions for such reconstruction in terms of the eigenvalue and the ball radius. We show that in the case where values of an eigenfunction are given on a sphere of radius equal to the corresponding eigenvalue, all values of the eigenfunction can be reconstructed; similarly to the previous case, sufficient numerical conditions are presented.

We propose a method for providing anonymity and security of data transmission in networks with network coding with multiple sources and receivers. An external passive adversary is assumed to be present in the network. It is required to organize message transmission in such a manner that the adversary cannot trace a message route. The proposed method is a modification of a secure transmission scheme based on coset coding. We show that using an additional operation at relaying nodes enables to remove statistical dependence between incoming and outgoing messages of the relaying nodes. This makes tracing message routes impossible. An overlay network between a source and a receiver must be constructed due to restrictions on routes between the source and receiver: the minimum cut between two successive nodes must be not less than the number of packets in the encoded source message.