Covering arrays and intersecting codes

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2^t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Rényi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.     

Construction of highly nonlinear resilient S-boxes with given degree

We provide two new construction methods for nonlinear resilient S-boxes with given degree. The first method is based on the use of linear error correcting codes together with highly nonlinear S-boxes. Given a [u, m, t + 1] linear code where u = n?d?1, d > m, we show that it is possible to construct (n, m, t, d) resilient S-boxes which have currently best known nonlinearity. Our second construction provides highly nonlinear (n, m, t, d) resilient S-boxes which do not have linear structure, then an improved version of this construction is given.     

Self-Orthogonal and Self-Dual Codes Constructed via Combinatorial Designs and Diophantine Equations

Combinatorial designs have been widely used, in the construction of self-dual codes. Recently, new methods of constructing self-dual codes are established using orthogonal designs (ODs), generalized orthogonal designs (GODs), a set of four sequences and Diophantine equations over GF(p). These methods had led to the construction of many new self-dual codes over small finite fields and rings. In this paper, we used some methods to construct self-orthogonal and self dual codes over GF(p), for some primes p. The construction is achieved by using some special kinds of combinatorial designs like orthogonal designs and GODs. Moreover, we combine eight circulant matrices, a system of Diophantine equations over GF(p), and a recently discovered array to obtain a new construction method. Using this method new self-dual and self-orthogonal codes are obtained. Specifically, we obtain new self-dual codes [32,16,12] over GF(11) and GF(13) which improve the previously known distances.     

New constructions for perfect hash families and related structures using combinatorial designs and codes

In this paper, we consider explicit constructions of perfect hash families using combinatorial methods. We provide several direct constructions from combinatorial structures related to orthogonal arrays. We also simplify and generalize a recursive construction due to Atici, Magliversas, Stinson and Wei [3]. Using similar methods, we also obtain efficient constructions for separating hash families which result in improved existence results for structures such as separating systems, key distribution patterns, group testing algorithms, cover‐free families and secure frameproof codes. © 2000 John Wiley & Sons, Inc. J Combin Designs 8:189–200, 2000     

Bounds for the Multicovering Radii of Reed-Muller Codes with Applications to Stream Ciphers

The multicovering radii of a code are recentgeneralizations of the covering radius of a code. For positivem, the m-covering radius of C is the leastradius t such that everym-tuple of vectors is contained in at least one ball of radiust centered at some codeword. In this paper upper bounds arefound for the multicovering radii of first order Reed-Muller codes. These bounds generalize the well-known Norse bounds for the classicalcovering radii of first order Reed-Muller codes. They are exactin some cases. These bounds are then used to prove the existence of secure families of keystreams against a general class of cryptanalytic attacks. This solves the open question that gave rise to the study ofmulticovering radii of codes.     

Infinite families of 3-designs from a type of five-weight code

It has been known for a long time that t-designs can be employed to construct both linear and nonlinear codes and that the codewords of a fixed weight in a code may hold a t-design. While a lot of progress in the direction of constructing codes from t-designs has been made, only a small amount of work on the construction of t-designs from codes has been done. The objective of this paper is to construct infinite families of 2-designs and 3-designs from a type of binary linear codes with five weights. The total number of 2-designs and 3-designs obtained in this paper are exponential in any odd m and the block size of the designs varies in a huge range.     

A construction of balanced arrays of strengtht and some related incomplete block designs

Summary Saha [6] has shown the equivalence between a ‘tactical system’ (or at-design) and a 2-symbol balanced array (BA) of strengtht. The implicit method of construction of BA in that paper has been generalized herein to that of ans-symbol BA of strengtht. Some BIB and PBIB designs are also constructed from these arrays. Majindar [2], Vanstone [8] and Saha [6] have all shown that the existence of a symmetrical BIBD forv treatments implies the existence of six more BIBD's forv treatments in (v/2) blocks. An analogue of this result has been obtained for a large class of PBIB designs in this paper.     

On linear programming bounds for nets

It is well known that there are close connections between low-discrepancy point sets and sequences on the one hand, and certain combinatorial and algebraic structures on the other hand. E. g., Niederreiter [1] showed the equivalence between (t, t + 2, s)-nets and orthogonal arrays of strength 2. Some years later this was generalized and made precise in the work of Lawrence [2] as well as Mullen and Schmid [3] by introducing ordered orthogonal arrays. This large class of combinatorial structures yields both new constructions and bounds for the existence of nets and sequences. The linear programming bound for ordered orthogonal arrays was first derived by Martin and Stinson [4]. As in the case of error-correcting codes and orthogonal arrays, it yields a very strong bound for ordered orthogonal arrays, and consequently for nets and sequences. Solving linear programming problems in exact arithmetics is very time-consuming. Using different approaches to reduce the computing time, we have calculated the linear programming bound for a wide parameter range. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

G-covering systems of subgroups for the class of supersoluble groups

Let ? be a class of groups. Given a group G, assign to G some set of its subgroups Σ = Σ(G). We say that Σ is a G-covering system of subgroups for ? (or, in other words, an ?-covering system of subgroups in G) if G ∈ ? wherever either Σ = ? or Σ ≠ ? and every subgroup in Σ belongs to ?. In this paper, we provide some nontrivial sets of subgroups of a finite group G which are G-covering subgroup systems for the class of supersoluble groups. These are the generalizations of some recent results, such as in [1–3].     

Constructions for Permutation Codes in Powerline Communications

A permutation array (or code) of length n and distance d is a set Γ of permutations from some fixed set of n symbols such that the Hamming distance between each distinct x, y ∈ Γ is at least d. One motivation for coding with permutations is powerline communication. After summarizing known results, it is shown here that certain families of polynomials over finite fields give rise to permutation arrays. Additionally, several new computational constructions are given, often making use of automorphism groups. Finally, a recursive construction for permutation arrays is presented, using and motivating the more general notion of codes with constant weight composition.     

On binary self-dual codes of lengths 60, 62, 64 and 66 having an automorphism of order 9

A method for constructing binary self-dual codes having an automorphism of order p ² for an odd prime p is presented in (S. Bouyuklieva et al. IEEE. Trans. Inform. Theory, 51, 3678–3686, 2005). Using this method, we investigate the optimal self-dual codes of lengths 60 ≤ n ≤ 66 having an automorphism of order 9 with six 9-cycles, t cycles of length 3 and f fixed points. We classify all self-dual [60,30,12] and [62,31,12] codes possessing such an automorphism, and we construct many doubly-even [64,32,12] and singly-even [66,33,12] codes. Some of the constructed codes of lengths 62 and 66 are with weight enumerators for which the existence of codes was not known until now.      

Families of twisted tensor product codes

Using geometric properties of the variety ${\mathcal V_{r,t}}$ , the image under the Grassmannian map of a Desarguesian (t ? 1)-spread of PG(rt ? 1, q), we introduce error correcting codes related to the twisted tensor product construction, producing several families of constacyclic codes. We determine the precise parameters of these codes and characterise the words of minimum weight.     

On the existence of uncountably many matroidal families

A matroidal family is a set $\text{F}$ ≠ ? of connected finite graphs such that for every finite graph G the edge-sets of those subgraphs of G which are isomorphic to some element of $\text{F}$ are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.     

Constructing strength three covering arrays with augmented annealing

A covering arrayCA(N;t,k,v) is an N×k array such that every N×t sub-array contains all t-tuples from v symbols at least once, where t is the strength of the array. One application of these objects is to generate software test suites to cover all t-sets of component interactions. Methods for construction of covering arrays for software testing have focused on two main areas. The first is finding new algebraic and combinatorial constructions that produce smaller covering arrays. The second is refining computational search algorithms to find smaller covering arrays more quickly. In this paper, we examine some new cut-and-paste techniques for strength three covering arrays that combine recursive combinatorial constructions with computational search; when simulated annealing is the base method, this is augmented annealing. This method leverages the computational efficiency and optimality of size obtained through combinatorial constructions while benefiting from the generality of a heuristic search. We present a few examples of specific constructions and provide new bounds for some strength three covering arrays.     

Unifying some known infinite families of combinatorial 3-designs

In this paper we present a construction of 3-designs by using a 3-design with resolvability. The basic construction generalizes a well-known construction of simple 3-(v,4,3) designs by Jungnickel and Vanstone (1986). We investigate the conditions under which the designs obtained by the basic construction are simple. Many infinite families of simple 3-designs are presented, which are closely related to some known families by Iwasaki and Meixner (1995), Laue (2004) and van Tran (2000, 2001). On the other hand, the designs obtained by the basic construction possess various properties: A theory of constructing simple cyclic 3-(v,4,3) designs by Köhler (1981) can be readily rebuilt from the context of this paper. Moreover many infinite families of simple resolvable 3-designs are presented in comparison with some known families. We also show that for any prime power q and any odd integer n there exists a resolvable 3-(qn+1,q+1,1) design. As far as the authors know, this is the first and the only known infinite family of resolvable t-(v,k,1) designs with t?3 and k?5. Those resolvable designs can again be used to obtain more infinite families of simple 3-designs through the basic construction.     

Parameters for which the Griesmer bound is not sharp

We prove for a large class of parameters t and r that a multiset of at most tθ_d-k+rθ_d-k-2 points in PG(d,q) that blocks every k-dimensional subspace at least t times must contain a sum of t subspaces of codimension k.We use our results to identify a class of parameters for linear codes for which the Griesmer bound is not sharp. Our theorem generalizes the non-existence results from Maruta [On the achievement of the Griesmer bound, Des. Codes Cryptogr. 12 (1997) 83-87] and Klein [On codes meeting the Griesmer bound, Discrete Math. 274 (2004) 289-297].     

Strongly regular Cayley graphs and rationality of relative Gauss sums

In this note, we give a construction of strongly regular Cayley graphs. The presented construction is based on choosing cyclotomic classes in finite fields, and our results generalize ten of the eleven sporadic examples of cyclotomic strongly regular graphs given by Schmidt and White [B. Schmidt, C. White, All two-weight irreducible cyclic codes, Finite Fields Appl. 8 (2002), 321–367] into infinite families. These infinite families of strongly regular graphs have new parameters. The main tools that we employed are relative Gauss sums instead of explicit evaluations of Gauss sums.     

Further results on the covering radius of small codes

The minimum number of codewords in a code with t ternary and b binary coordinates and covering radius R is denoted by K(t,b,R). In the paper, necessary and sufficient conditions for K(t,b,R)=M are given for M=6 and 7 by proving that there exist exactly three families of optimal codes with six codewords and two families of optimal codes with seven codewords. The cases M?5 were settled in an earlier study by the same authors. For binary codes, it is proved that K(0,2b+4,b)?9 for b?1. For ternary codes, it is shown that K(3t+2,0,2t)=9 for t?2. New upper bounds obtained include K(3t+4,0,2t)?36 for t?2. Thus, we have K(13,0,6)?36 (instead of 45, the previous best known upper bound).     

Analysis and Solving SAT and MAX-SAT Problems Using an L-partition Approach

In this paper, we study SAT and MAX-SAT using the integer linear programming models and L-partition approach. This approach can be applied to analyze and solve many discrete optimization problems including location, covering, scheduling problems. We describe examples of SAT and MAX-SAT families for which the cardinality of L-covering of the relaxation polytope grows exponentially with the number of variables. These properties are useful in analysis and development of algorithms based on the linear relaxation of the problems. Besides we present the L-class enumeration algorithm for SAT using the L-partition approach. In addition we consider an application of this algorithm to construct exact algorithm and local search algorithms for the MAX-SAT problem.     

More on the inadmissibility of step-up

Cohen and Sackrowitz [Characterization of Bayes procedures for multiple endpoint problems and inadmissibility of the step-up procedure, Ann. Statist. 33 (2005) 145-158] proved that the step-up multiple testing procedure is inadmissible for a multivariate normal model with unknown mean vector and known intraclass covariance matrix. The hypotheses tested are each mean is zero vs. each mean is positive. The risk function is a 2×1 vector where one component is average size and the other component is one minus average power. In this paper, we extend the inadmissibility result to several different models, to two-sided alternatives, and to other risk functions. The models include one-parameter exponential families, independent t-variables, independent χ²-variables, t-tests arising from the analysis of variance, and t-tests arising from testing treatments against a control. The additional risk functions are linear combinations where one component is the false discovery rate (FDR).