Bounds on the rate of separating codes

A code with words in a finite alphabet is said to be an (s, l) separating code if for any two disjoint collections of its words of size at most s and l, respectively, there exists a coordinate in which the set of symbols of the first collection do not intersect the set of symbols of the second. The main goal of the paper is obtaining new bounds on the rate of (s, l) separating codes. Bounds on the rate of binary (s, l) separating codes, the most important for applications, are studied in more detail. We give tables of numerical values of the best presently known bounds on the rate.     

Propelinear codes related to some classes of optimal codes

A code is said to be propelinear if its automorphism group contains a subgroup that acts regularly on codewords. We show propelinearity of complements of cyclic codes C _1,i , (i, 2 ^m ? 1) = 1, of length n = 2 ^m ? 1, including the primitive two-error-correcting BCH code, to the Hamming code; the Preparata code to the Hamming code; the Goethals code to the Preparata code; and the Z₄-linear Preparata code to the Z₄-linear perfect code.     

Optimal Path Embedding in the Exchanged Crossed Cube

The (s + t + 1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s ≥ 3, t ≥ 3, for any two different vertices, all paths whose lengths are between \( \max \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2 ^s+t+1 ? 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +2 \). The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQ _n .     

Tracking frequent items over distributed probabilistic data

Tracking frequent items (also called heavy hitters) is one of the most fundamental queries in real-time data due to its wide applications, such as logistics monitoring, association rule based analysis, etc. Recently, with the growing popularity of Internet of Things (IoT) and pervasive computing, a large amount of real-time data is usually collected from multiple sources in a distributed environment. Unfortunately, data collected from each source is often uncertain due to various factors: imprecise reading, data integration from multiple sources (or versions), transmission errors, etc. In addition, due to network delay and limited by the economic budget associated with large-scale data communication over a distributed network, an essential problem is to track the global frequent items from all distributed uncertain data sites with the minimum communication cost. In this paper, we focus on the problem of tracking distributed probabilistic frequent items (TDPF). Specifically, given k distributed sites S = {S ₁, … , S _k }, each of which is associated with an uncertain database \(\mathcal {D}_{i}\) of size n _i , a centralized server (or called a coordinator) H, a minimum support ratio r, and a probabilistic threshold t, we are required to find a set of items with minimum communication cost, each item X of which satisfies P r(s u p(X) ≥ r × N) > t, where s u p(X) is a random variable to describe the support of X and \(N={\sum }_{i=1}^{k}n_{i}\). In order to reduce the communication cost, we propose a local threshold-based deterministic algorithm and a sketch-based sampling approximate algorithm, respectively. The effectiveness and efficiency of the proposed algorithms are verified with extensive experiments on both real and synthetic uncertain datasets.     

On horizons and wormholes in k-essence theories

We study the properties of possible static, spherically symmetric configurations in k-essence theories with the Lagrangian functions of the form F(X), X ≡ ?,_α ?,^α. A no-go theorem has been proved, claiming that a possible black-hole-like Killing horizon of finite radius cannot exist if the function F(X) is required to have a finite derivative dF/dX. Two exact solutions are obtained for special cases of kessence: one for F(X) = F ₀ X ^1/3, another for F(X) = F ₀|X|^1/2 ? 2Λ, where F ₀ and Λ are constants. Both solutions contain horizons, are not asymptotically flat, and provide illustrations for the obtained nogo theorem. The first solution may be interpreted as describing a black hole in an asymptotically singular space-time, while in the second solution two horizons of infinite area are connected by a wormhole.     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

Tolerance limits on order statistics in future samples coming from the Pareto distribution

It is often desirable to have statistical tolerance limits available for the distributions used to describe time-to-failure data in reliability problems. For example, one might wish to know if at least a certain proportion, say β, of a manufactured product will operate at least T hours. This question cannot usually be answered exactly, but it may be possible to determine a lower tolerance limit L(X), based on a random sample X, such that one can say with a certain confidence γ that at least 100β% of the product will operate longer than L(X). Then reliability statements can be made based on L(X), or, decisions can be reached by comparing L(X) to T. Tolerance limits of the type mentioned above are considered in this paper, which presents a new approach to constructing lower and upper tolerance limits on order statistics in future samples. Attention is restricted to invariant families of distributions under parametric uncertainty. The approach used here emphasizes pivotal quantities relevant for obtaining tolerance factors and is applicable whenever the statistical problem is invariant under a group of transformations that acts transitively on the parameter space. It does not require the construction of any tables and is applicable whether the past data are complete or Type II censored. The proposed approach requires a quantile of the F distribution and is conceptually simple and easy to use. For illustration, the Pareto distribution is considered. The discussion is restricted to one-sided tolerance limits. A practical example is given.     

Discrete Product Inventory Control System with Positive Service Time and Two Operation Modes

Consideration is given to the Markov inventory control system of a discrete product of maximum volume S under the strategies (s,Q) and (s, S) with a positive service time. Upon arrival, the order is queued if the inventory level is positive or, otherwise, leaves the system unserviced. One server handles the queued orders one-by-one in the sequence of their arrival. If the inventory level exceeds s, then the service time has the exponential distribution of intensity μ; otherwise, of intensity αμ, 0 < α ? 1. The product in the inventory is consumed only at the instant when the service (of the order) ends. Inventory deficit is not allowed. When the inventory is empty new orders are not admitted into the system, and the service process of the queued orders (if any) is stopped. The lead time is assumed to be exponentially distributed. Analytical relations are established for the basic stationary performance characteristics of the system.     

List decoding of the first-order binary Reed-Muller codes

A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 ? ?) about the received vector and has the complexity of O(n ln²(min{? ^?2, n})) binary operations.     

One-Nonterminal Conjunctive Grammars over a Unary Alphabet

Systems of equations of the form X _i =φ _i (X ₁,…,X _n ) (1≤ i ≤ n) are considered, in which the unknowns are sets of natural numbers. Expressions φ _i may contain the operations of union, intersection and elementwise addition \(S+T=\{m+n\mid m\in S\), n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.     

On weak isometries of Preparata codes

Two codes C ₁ and C ₂ are said to be weakly isometric if there exists a mapping J: C ₁ → C ₂ such that for all x, y in C ₁ the equality d(x, y) = d holds if and only if d(J(x), J(y)) = d, where d is the code distance of C ₁. We prove that Preparata codes of length n ≥ 2¹² are weakly isometric if and only if the codes are equivalent. A similar result is proved for punctured Preparata codes of length at least 2¹⁰ ? 1.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

On some extremal problems for mutual information and entropy

The problem of determining the maximum mutual information I(X; Y) and minimum entropy H(X, Y) of a pair of discrete random variables X and Y is considered under the condition that the probability distribution of X is fixed and the error probability Pr{Y ≠ X} takes a given value ε, 0 ≤ ε ≤ 1. Precise values for these quantities are found, which in several cases allows us to obtain explicit formulas for both the maximum information and minimum entropy in terms of the probability distribution of X and the parameter ε.     

On risk concentration for convex combinations of linear estimators

We consider the estimation problem for an unknown vector β ∈ Rp in a linear model Y = Xβ + σξ, where ξ ∈ Rⁿ is a standard discrete white Gaussian noise and X is a known n × p matrix with n ≥ p. It is assumed that p is large and X is an ill-conditioned matrix. To estimate β in this situation, we use a family of spectral regularizations of the maximum likelihood method β^α(Y) = H ^α(X ^T X) β ^?(Y), α ∈ R⁺, where β ^?(Y) is the maximum likelihood estimate for β and {H ^α(·): R⁺ → [0, 1], α ∈ R⁺} is a given ordered family of functions indexed by a regularization parameter α. The final estimate for β is constructed as a convex combination (in α) of the estimates β^α(Y) with weights chosen based on the observations Y. We present inequalities for large deviations of the norm of the prediction error of this method.     

Combinatorial methods for constructing bipartite uniform minimal quasicomplete graphs (symmetrical block designs)

Consideration was given to a specific family of bipartite graphs consisting of two disjoint subsets X and Y of vertices and characterized by that each vertex in X (Y) is connected to each of the remaining vertices in X (Y) by a unique path of length two passing through some vertex in Y (X). The prefix “quasi” reflects the fact that complete connection of the vertices is realized by paths of length two rather than by edges. The problem of constructing uniform minimal graphs with identical cardinalities of the subsets X and Y which is of practical interest for complex communication networks was discussed. It belongs to the class of combinatorial problems of construction of the so-called symmetrical block designs.     

Embedding cycles and paths on solid grid graphs

Despite many algorithms for embedding graphs on unbounded grids, only a few results on embedding graphs on restricted grids have been published. In this paper, we study the problem of embedding paths and cycles on solid grid graphs. We show that a cycle of length k is unit-length embeddable on a solid grid graph G if k is an even integer between four and the length of the longest cycle of G. In addition, our result shows that a path of length k is unit-length embeddable on G, between its two given vertices s and t, if \(k\le L\) and \(k\equiv L (\mathrm{mod}\ 2)\), in which L is the length of the longest path between s and t. Our presented two algorithms show that such embeddings can be found in linear time for cycles and quadratic time for paths, with respect to the size of graph G. In the case of rectangular grid graphs, the running time of the algorithms can be improved to O(k) and O\((k^2)\), respectively. In addition, we extend our results to \(m\times n\times o\) 3D grids. A application of our result is in the interconnection network mapping in parallel processing.     

MDS codes in Doob graphs

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 ₄ 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 ³/36+7m ²/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).     

On stable exponential solutions in Einstein–Gauss–Bonnet cosmology with zero variation of <Emphasis Type="Italic">G</Emphasis>

A D-dimensional gravitational model with a Gauss–Bonnet term and the cosmological constant Λ is considered. Assuming diagonal cosmological metrics, we find, for certain Λ > 0, new examples of solutions with an exponential time dependence of two scale factors, governed by two Hubble-like parameters H > 0 and h < 0, corresponding to submanifolds of dimensions m and l, respectively, with (m, l) = (4, 2), (5, 2), (5, 3), (6, 7), (7, 5), (7, 6) and D = 1 + m + l. Any of these solutions describes an exponential expansion of our 3-dimensional factor space with the Hubble parameter H and zero variation of the effective gravitational constant G. We also prove the stability of these solutions in the class of cosmological solutions with diagonal metrics.     

(<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-Distance Antimagic Labeling of Some Types of Graphs

We analyze the necessary existence conditions for (a, d)-distance antimagic labeling of a graph G = (V, E) of order n. We obtain theorems that expand the family of not (a, d) -distance antimagic graphs. In particular, we prove that the crown P _n ○ P ₁ does not admit an (a, 1)-distance antimagic labeling for n ≥ 2 if a ≥ 2. We determine the values of a at which path P _n can be an (a, 1)-distance antimagic graph. Among regular graphs, we investigate the case of a circulant graph.     

On Some Optimization Problems for the Rényi Divergence

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 } = α.