New Technique for Decoding Codes in the Rank Metric and Its Cryptography Applications

We present two new algorithms for decoding an arbitrary (n, k) linear rank distance code over GF(q ^N ). These algorithms correct errors of rank r in O((Nr)³ q ^(r–1)(k+1)) and O((k + r)³ r ³ q ^{(r–1)(N–r)}) operations in GF(q) respectively. The algorithms give one of the most efficient attacks on public-key cryptosystems based on rank codes, as well as on the authentication scheme suggested by Chen.     

New Minimum Distance Bounds for Linear Codes over Small Fields

Let [n, k, d] _q -codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper we consider codes over GF(3), GF(5), GF(7), and GF(8). Over GF(3), three new linear codes are constructed. Over GF(5), eight new linear codes are constructed and the nonexistence of six codes is proved. Over GF(7), the existence of 33 new codes is proved. Over GF(8), the existence of ten new codes and the nonexistence of six codes is proved. All of these results improve the corresponding lower and upper bounds in Brouwer's table [www.win.tue.nl/aeb/voorlincod.html].     

A generalization of concavity for finite differences

The concept of concavity is generalized to discrete functions, u, satisfying the n^th-order difference inequality, (−1)^n−kΔⁿu(m) ≥ 0, M = 0, 1,..., N and the homogeneous boundary conditions, u(0) = … = u(k−1) = 0, u(N + k + 1) = … = u(N + n) = 0 for some k “1, …, n − 1”. A piecewise polynomial is constructed which bounds u below. The piecewise polynomial is employed to obtain a positive lower bound on u(m) for m = k, …, N + k, where the lower bound is proportional to the supremum of u. An analogous bound is obtained for a related Green's function.     

New Quasi-cyclic Degenerate Linear Codes over GF(8)

Let [n, k, d] _q code be a linear code of length n, dimension k, and minimum Hamming distance d over GF(q). One of the most important problems in coding theory is to construct codes with best possible minimum distances. Recently, quasi-cyclic (QC) codes were proved to contain many such codes. In this paper, twenty-five new codes over GF(8) are constructed, which improve the best known lower bounds on minimum distance.     

One-step t-fault diagnosis for hypermesh optical interconnection multiprocessor systems

To maintain high reliability and availability, system-level diagnosis should be considered for the multiprocessor systems. The self-diagnosis problem of hypermesh, emerging potential optical interconnection networks for multiprocessor systems, is solved in this paper. We derive that the precise one-step diagnosability of kⁿ-hypermesh is n(k − 1). Based on the principle of cycle decomposition, a one-step t-fault diagnosis algorithm for kⁿ-hypermesh which runs in O(kⁿn(k − 1)) time also is described.     

Worst-case identification in ℓ2: linear and nonlinear algorithms

We consider worst-case identification in the ℓ₂ norm. Given an unknown system h ε ℓ₁ one wishes to choose bounded inputs u ε ℓ∞ such that given finitely many corrupted output measurements {y(k): 0 ≤ k}of Y = h*u + η, where η is noise, assumed small, one can construct an approximation g with g - h₂ → 0 as η∞ → 0 and n → ∞. It is shown that inputs can be chosen such that to identify a sequence of length n with an ℓ₂ error of O(η∞) one requires only O(n) measurements. A numerical example is inclu     

Permutation routing in double-loop networks: design and empirical evaluation

A double-loop network is an undirected graph whose nodes are integers 0,1,…,n−1 and each node u is adjacent to four nodes u±h₁(mod>n), u±h₂(mod>n), where 0<h₁<h₂<n/2. There are initially n packets, one at each of the n nodes. The packet at node u is destined to node π(u), where the mapping uπ(u) is a permutation. The aim is to minimize the number of routing steps to route all the packets to their destinations. If ℓ is the tight lower bound for this number, then the best known permutation routing algorithm takes, on average, 1.98ℓ routing steps (and 2ℓ routing steps in the worst-case).Because the worst-case complexity cannot be improved, we design four new static permutation routing algorithms with gradually improved average-case performances, which are 1.37ℓ, 1.35ℓ, 1.18ℓ, and 1.12ℓ. Thus, the best of these algorithms exceeds the optimal routing by at most 12% on average.To support our algorithm design we develop a program which simulates permutation routing in a network according to the given topology, routing model as well as communication pattern and measure several quality criteria. We have tested our algorithms on a large number of double-loop networks and permutations (randomly generated and standard).     

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199–233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 2^3k2+O(k)·n2^{3k^{2}+O(k)}\cdot n arithmetic operations and can be efficiently implemented in parallel.     

Monoid-labeled transition systems

Given a -complete (semi)lattice , we consider -labeled transition systems as coalgebras of a functor ⁽⁻⁾, associating with a set X the set ^X of all -fuzzy subsets. We describe simulations and bisimulations of -coalgebras to show that L⁽⁻⁾ weakly preserves nonempty kernel pairs iff it weakly preserves nonempty pullbacks iff L is join infinitely distributive (JID).Exchanging for a commutative monoid , we consider the functor ⁽⁻⁾_ω which associates with a set X all finite multisets containing elements of X with multiplicities m M. The corresponding functor weakly preserves nonempty pullbacks along injectives iff 0 is the only invertible element of , and it preserves nonempty kernel pairs iff is refinable, in the sense that two sum representations of the same value, r₁ + … + r_m = c₁ + … + c_n, have a common refinement matrix (m_{(i, j)}) whose k-th row sums to r_k and whose l-th column sums to c_l for any 1≤ k ≤ m and 1 ≤ l ≤ n.     

Special classes of separable Goppa codes with improved parameter estimates

We show that subclasses of q-ary separable Goppa codes Γ(L, G) with L = {α ∈ GF(q ^2ℓ): G(α) ∈ 0} and with special Goppa polynomials G(x) can be represented as a chain of equivalent and embedded codes. For all codes of the chain we obtain an improved bound for the dimension and find an exact value of the minimum distance. A chain of binary codes is considered as a particular case with specific properties.     

A further result on the oscillation of delay difference equations

In this paper, we are concerned with the delay difference equations of the form

(*)

y_n+1 − y_n + p_ny_n−k = 0, N = 0, 1, 2, …,

(*)where p_n ≥ 0 and k is a positive integer. We prove by using a new technique that

guarantees that all solutions of equation (*) oscillate, which improves many previous well-known results. In particular, our theorems also fit the case where Σⁿ⁻¹_i=n−kp_i ≤ k^k+1/(k + 1)^k+1. In addition, we present a nonoscillation sufficient condition for equation (*).     

Symmetric Rank Codes

As is well known, a finite field _n = GF(q ⁿ ) can be described in terms of n × n matrices A over the field = GF(q) such that their powers A ⁱ , i = 1, 2, ..., q ⁿ – 1, correspond to all nonzero elements of the field. It is proved that, for fields _n of characteristic 2, such a matrix A can be chosen to be symmetric. Several constructions of field-representing symmetric matrices are given. These matrices A ⁱ together with the all-zero matrix can be considered as a _n -linear matrix code in the rank metric with maximum rank distance d = n and maximum possible cardinality q ⁿ . These codes are called symmetric rank codes. In the vector representation, such codes are maximum rank distance (MRD) linear [n, 1, n] codes, which allows one to use known rank-error-correcting algorithms. For symmetric codes, an algorithm of erasure symmetrization is proposed, which considerably reduces the decoding complexity as compared with standard algorithms. It is also shown that a linear [n, k, d = n – k + 1] MRD code _k containing the above-mentioned one-dimensional symmetric code as a subcode has the following property: the corresponding transposed code is also _n -linear. Such codes have an extended capability of correcting symmetric errors and erasures.     

To the Metrical Rigidity of Binary Codes

A code C in the n-dimensional metric space E ⁿ over GF(2) is called metrically rigid if each isometry I : C E ⁿ can be extended to an isometry of the whole space E ⁿ . For n large enough, metrical rigidity of any length-n binary code that contains a 2-(n, k, )-design is proved. The class of such codes includes, for instance, all families of uniformly packed codes of large enough lengths that satisfy the condition d – 2, where d is the code distance and is the covering radius.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.     

New One-Generator Quasi-cyclic Codes over GF(7)

Let [n,k,d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). In this paper, seventeen new codes are constructed, which improve the known lower bounds on minimum distance.     

Projective Linear Groups as Galois Groups overQvia Modular Representations

We give an algorithm for the determination of the finitely many primes such that the image of the modular Galois representations attached to a weight 2 newform on Γ₀(N) without complex multiplication or inner twists may not be “as large as possible". We apply the algorithm to suitable newforms and we obtain the realization of the groups PSL(2,F_ℓ²),PGL (2,F_ℓ³) andPSL (2,F_ℓ⁴) as Galois groups overQfor high density sets of primes.     

Existence of triple positive solutions of two-point right focal boundary value problems on time scales

We consider the following boundary value problem, (−1)ⁿ⁻¹y^Δn(t)=(−1)^p+1F(t,y(σⁿ⁻¹(t))),t[a,b]∩T, y^Δn(a)=0,0≤i≤p−1, y^Δn(σ(b))=0,p≤i≤n−1,where n ≥ 2, 1 ≤ p ≤ n - 1 is fixed and T is a time scale. By applying fixed-point theorems for operators on a cone, existence criteria are developed for triple positive solutions of the boundary value problem. We also include examples to illustrate the usefulness of the results obtained.     

Lower Bounds for Merging Networks

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach.23, 566–571) is solved: lim_n→∞M(m, n)/n=log m/2+m/2^{log m}.     

Self-checking circuits and decoding algorithms for binary hamming and BCH codes and Reed-Solomon codes over GF(2 m )

We consider problems of detecting errors in combinational circuits and algorithms for the decoding of linear codes. We show that a totally self-checking combinatorial circuit for the decoding of a binary Hamming [n, k] code can be constructed if and only if n = 2 ^r ? 1, r = n?k. We introduce the notion of a totally self-checking combinational circuit detecting error clusters of size at most µ; for shortened Hamming [n,k] codes, we construct totally self-checking decoding combinational circuits detecting error clusters of size at most µ, 2 ≤ µ < n?k. We describe single-error protected and self-checking algorithms: the extended Euclidean algorithm and decoding algorithms for binary BCH codes and Reed-Solomon codes over GF(2 ^m ).     

Finding an Euclidean anti--centrum location of a set of points

An obnoxious facility is to be located inside a polygonal region of the plane, maximizing the sum of the k smallest weighted Euclidean distances to n given points, each protected by some polygonal forbidden region. For the unweighted case and k fixed an O(n²logn) time algorithm is presented. For the weighted case a thorough study of the relevant structure of the multiplicatively weighted order-k-Voronoi diagram leads to the design of an O(kn³+n³logn) time algorithm for finding an optimal solution to the anti-t-centrum problem for every t=1,…,k, simultaneously.