Polar Codes with Higher-Order Memory

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 }}})\) 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.     

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

Central limit theorem and large deviations of the fading Wyner cellular model via product of random matrices theory

We apply the theory of products of random matrices to the analysis of multi-user communication channels similar to the Wyner model, which are characterized by short-range intra-cell broadcasting. We study fluctuations of the per-cell sum-rate capacity in the non-ergodic regime and provide results of the type of the central limit theorem (CLT) and large deviations (LD). Our results show that CLT fluctuations of the per-cell sum-rate C _m are of order \(1/\sqrt m \), where m is the number of cells, whereas they are of order 1/m in classical random matrix theory. We also show an LD regime of the form P(|C _m ? C| > ?) ≤ e ^?mα with α = α(?) > 0 and C = \(\mathop {\lim }\limits_{m \to \infty } \) C _m , as opposed to the rate \(e^{ - m^2 \alpha } \) in classical random matrix theory.     

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks

We address the problem of minimizing power consumption when broadcasting a message from one node to all the other nodes in a radio network. To enable power savings for such a problem, we introduce a compelling new data streaming problem which we call the Bad Santa problem. Our results on this problem apply for any situation where: (1) a node can listen to a set of n nodes, out of which at least half are non-faulty and know the correct message; and (2) each of these n nodes sends according to some predetermined schedule which assigns each of them its own unique time slot. In this situation, we show that in order to receive the correct message with probability 1, it is necessary and sufficient for the listening node to listen to a \(\Theta(\sqrt{n})\) expected number of time slots. Moreover, if we allow for repetitions of transmissions so that each sending node sends the message O(log?^? n) times (i.e. in O(log?^? n) rounds each consisting of the n time slots), then listening to O(log?^? n) expected number of time slots suffices. We show that this is near optimal.We describe an application of our result to the popular grid model for a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message m, all awake nodes within L _∞ distance r receive m. In this model, up to \(t<\frac{r}{2}(2r+1)\) nodes within any 2r+1 by 2r+1 square in the grid can suffer Byzantine faults. Moreover, we assume that the nodes that suffer Byzantine faults are chosen and controlled by an adversary that knows everything except for the random bits of each non-faulty node. This type of adversary models worst-case behavior due to malicious attacks on the network; mobile nodes moving around in the network; or static nodes losing power or ceasing to function. Let n=r(2r+1). We show how to solve the broadcast problem in this model with each node sending and receiving an expected \(O(n\log^{2}{|m|}+\sqrt{n}|m|)\) bits where |m| is the number of bits in m, and, after broadcasting a fingerprint of m, each node is awake only an expected \(O(\sqrt{n})\) time slots. Moreover, for t≤(1?ε)(r/2)(2r+1), for any constant ε>0, we can achieve an even better energy savings. In particular, if we allow each node to send O(log?^? n) times, we achieve reliable broadcast with each node sending O(nlog?²|m|+(log?^? n)|m|) bits and receiving an expected O(nlog?²|m|+(log?^? n)|m|) bits and, after broadcasting a fingerprint of m, each node is awake for only an expected O(log?^? n) time slots. Our results compare favorably with previous protocols that required each node to send Θ(|m|) bits, receive Θ(n|m|) bits and be awake for Θ(n) time slots.     

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.     

(<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 conditional diagnosability and reliability of the BC networks

An n-dimensional bijective connection network (in brief, BC network), denoted by X _n , is an n-regular graph with 2 ⁿ nodes and n2 ^n?1 edges. Hypercubes, crossed cubes, twisted cubes, and Möbius cubes all belong to the class of BC networks (Fan and He in Chin. J. Comput. 26(1):84–90, [2003]). We prove that the super connectivity of X _n is 2n?2 for n≥3 and the conditional diagnosability of X _n is 4n?7 for n≥5. As a corollary of this result, we obtain the super connectivity and conditional diagnosability of the hypercubes, twisted cubes, crossed cubes, and Möbius cubes.     

On (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis> )-Distance Anti-Magic and 1-Vertex Bimagic Vertex Labelings of Certain Types of Graphs

The results for the corona P _n ?°?P₁ are generalized, which make it possible to state that P _n ?°?P₁ is not an ( a, d)-distance antimagic graph for arbitrary values of a and d. A condition for the existence of an ( a, d)-distance antimagic labeling of a hypercube Q _n is obtained. Functional dependencies are found that generate this type of labeling for Q _n . It is proved by the method of mathematical induction that Q _n is a (2 ⁿ ?+?n???1,?n???2) -distance antimagic graph. Three types of graphs are defined that do not allow a 1-vertex bimagic vertex labeling. A relation between a distance magic labeling of a regular graph G and a 1-vertex bimagic vertex labeling of G?∪?G is established.     

Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

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.     

Observational constraints on a hyperbolic potential in brane-world inflation

We focus on the large field of a hyperbolic potential form, which is characterized by a parameter f, in the framework of the brane-world inflation in Randall-Sundrum-II model. From the observed form of the power spectrum P _R (k), the parameter f should be of order 0.1m _p to 0.001m _p , the brane tension must be in the range λ ~ (1?10)×10⁵⁷ GeV⁴, and the energy scale is around V₀ ^1/4 ~ 10¹⁵ GeV. We find that the inflationary parameters (n _s , r, and dn _s /d(ln k) depend only on the number of e-folds N. The compatibility of these parameters with the last Planck measurements is realized with large values of N.     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Minimizing the maximal weighted lateness of delivering orders between two railroad stations

We consider the planning problem for freight transportation between two railroad stations. We are required to fulfill orders (transport cars by trains) that arrive at arbitrary time moments and have different value (weight). The speed of trains moving between stations may be different. We consider problem settings with both fixed and undefined departure times for the trains. For the problem with fixed train departure times we propose an algorithm for minimizing the weighted lateness of orders with time complexity O(qn ² log n) operations, where q is the number of trains and n is the number of orders. For the problem with undefined train departure and arrival times we construct a Pareto optimal set of schedules optimal with respect to criteria wL _max and C _max in O(n ² max{n log n, q log v}) operations, where v is the number of time windows during which the trains can depart. The proposed algorithm allows to minimize both weighted lateness wL _max and total time of fulfilling freight delivery orders C _max.     

Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.     

Bimagic Vertex Labelings

The notion of the equivalence of vertex labelings on a given graph is introduced. The equivalence of three bimagic labelings for regular graphs is proved. A particular solution is obtained for the problem of the existence of a 1-vertex bimagic vertex labeling of multipartite graphs, namely, for graphs isomorphic with K_{n, n, m}. It is proved that the sequence of bi-regular graphs K_n(ij)?=?((K_n???1???M)?+?K₁)???(u_nu_i)???(u_nu_j) admits 1-vertex bimagic vertex labeling, where u_i, u_j is any pair of non-adjacent vertices in the graph K_n???1???M, u_n is a vertex of K₁, M is perfect matching of the complete graph K_n???1. It is established that if an r-regular graph G of order n is distance magic, then graph G + G has a 1-vertex bimagic vertex labeling with magic constants (n?+?1)(n?+?r)/2?+?n² and (n?+?1)(n?+?r)/2?+?nr. Two new types of graphs that do not admit 1-vertex bimagic vertex labelings are defined.     

Expansion of Self-Similar Functions in the Faber–Schauder System

Let Ω = A^N be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σ_k=1^∞|x _k ? y _k |2^?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p₀, p₁ > 0, p₀ + p₁ = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 ⁿ r ? j), j = 0,1,…, 2 ⁿ ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording.     

Sufficient Conditions for Monotonicity of the Undetected Error Probability for Large Channel Error Probabilities

The performance of a linear error-detecting code in a symmetric memoryless channel is characterized by its probability of undetected error, which is a function of the channel symbol error probability, involving basic parameters of a code and its weight distribution. However, the code weight distribution is known for relatively few codes since its computation is an NP-hard problem. It should therefore be useful to have criteria for properness and goodness in error detection that do not involve the code weight distribution. In this work we give two such criteria. We show that a binary linear code C of length n and its dual code C^⊥ of minimum code distance d^⊥ are proper for error detection whenever d^⊥ ≥ ?n/2? + 1, and that C is proper in the interval [(n + 1 ? 2d^⊥)/(n ? d^⊥); 1/2] whenever ?n/3? + 1 ≤ d^⊥ ≤ ?n/2?. We also provide examples, mostly of Griesmer codes and their duals, that satisfy the above conditions.     

A new strategy for generating shortest addition sequences

An addition sequence problem is given a set of numbers X = {n ₁, n ₂, . . . , n _m }, what is the minimal number of additions needed to compute all m numbers starting from 1? This problem is NP-complete. In this paper, we present a branch and bound algorithm to generate an addition sequence with a minimal number of elements for a set X by using a new strategy. Then we improve the generation by generalizing some results on addition chains (m = 1) to addition sequences and finding what we will call a presumed upper bound for each n _j , 1 ≤ j ≤ m, in the search tree.     

Asymptotic probability of encountering an accidental similarity in the presence of counter examples

Previously, we found the generating function of an accidental resemblance to the b parent examples at m counter examples [1]. In this paper, we restrict ourself to the case where b = 2 with equal success probabilities p in Bernoulli trials for all attributes of each counter example and a success probability р ² for each attribute in an accidental similarity. If the number n of attributes tends to infinity, the success probability is defined as \(p = \sqrt {a/n} \), and m = b√n counter examples are considered, then the probability of the occurrence of an accidental similarity avoiding these m counter examples tends to 1 ? e ^?a ? ae ^?a [1 ? e ^?b√a ]..