We consider graphs whose vertex set is the set of permutations of the first $n$ natural numbers. Two such sequences are adjacent if for two different natural numbers they and their images in the two permutations occupy four different positions in some specific order, implying that the permutations are different. Several such relations are investigated, and for two of them the precise asymptotic magnitude of the largest clique in the graph is determined.

We begin a systematic study of the problem of the zero-error capacity of noisy binary channels with memory and solve some of the non-trivial cases.

Since 2003, algebraic attacks have received a lot of attention in the cryptography literature. In this context, algebraic immunity quantifies the resistance of a Boolean function to the standard algebraic attack of the pseudo-random generators using it as a nonlinear Boolean function. A high value of algebraic immunity is now an absolutely necessary cryptographic criterion for a resistance to algebraic attacks but is not sufficient, because of more general kinds of attacks so-called Fast Algebraic Attacks. In view of these attacks, the study of the set of annihilators of a Boolean function has become very important. We show that studying the annihilators of a Boolean function can be translated into studying the codewords of a linear code. We then explain how to exploit that connection to evaluate or estimate the algebraic immunity of a cryptographic function. Direct links between the theory of annihilators used in algebraic attacks and coding theory are established using an atypical univariate approach.

At ICS 2010, Dziembowski et al. introduced the notion of Non-Malleable Codes (NMC), adapting the cryptographic notion of non-malleability to the coding theory. Using NMC, if an attacker modifies a codeword, decoding this modified codeword will return either the original message or a completely unrelated value. The property of non-malleability depends on a family of modifications authorized to the attacker. In their paper, Dziem-bowski et al. propose a construction valid for the family of all bit-wise independent functions. At ITW 2011, Chabanne et al. proposed another construction for non-malleable codes w.r.t. bit-wise independent tampering functions by drawing a parallel between NMC and the Wire-Tap Channel II. In this paper, we show that the construction using Linear Coset Coding proposed by Chabanne et al. is non-malleable w.r.t. a larger class of functions, by considering linear tampering. Our results are derived from security results on Secure Network Coding using Linear Coset Coding, introduced by El Rouayheb and Soljanin at ISIT 2007.

The average radius of a block code is a parameter that occurs naturally in quantization and steganography. We give asymptotic upper and lower bounds on this parameter. In particular we show that for almost all long codes the normalized average radius equals the normalized covering radius. We survey some special graph-theoretic lower bounds.

Recently, Dziembowski et al. introduced the notion of non-malleable codes (NMC), inspired from the notion of non-malleability in cryptography and the work of Gennaro et al. in 2004 on tamper proof security. Informally, when using NMC, if an attacker modifies a codeword, decoding this modified codeword will return either the original message or a completely unrelated value. The definition of NMC is related to a family of modifications authorized to the attacker. In their paper, Dziembowski et al. propose a construction valid for the family of all bit-wise independent functions. In this article, we study the link between the second version of the Wire-Tap (WT) Channel, introduced by Ozarow and Wyner in 1984, and NMC. Using coset-coding, we describe a new construction for NMC w.r.t. a subset of the family of bit-wise independent functions. Our scheme is easier to build and more efficient than the one proposed by Dziembowski et al.

The maximum size of a binary code is studied as a function of its lengthn, minimum distanced, and minimum codeword weight \ssiw. This functionB(n,d,w) is first characterized in terms of its exponential growth rate in the limitn→∞ for fixed δ =d/nand ω =w/n. The exponential growth rate ofB(n,d,w) is shown to be equal to the exponential growth rate ofA(n,d) for 0 ≤ ω ≤ 1/2, and equal to the exponential growth rate ofA(n,d,w) for 1/2B(n,d,w) are derived using the semidefinite programming (SDP) method. These bounds yield a nonasymptotic improvement of the second Johnson bound and are tight for certain values of the parameters.

We introduce a new class of problems lying halfway between questions about graph capacity and intersection. We say that two binary sequencesxandyof the same length have a skewincidence if there is a coordinateifor whichxi=yi+1=1 or vice versa. We give relatively close bounds on the maximum number of binary sequences of lengthnany pair of which has a skewincidence. A systematic study of these problems helps to understand the mathematical difficulties to solve zero-error problems in information theory.

Motivated by certain recent problems in asynchronous communication, we introduce and study B(n, d, w), defined as the maximum number of length n binary sequences with minimum distance d, and such that each sequence has weight at least w. Specifically, we investigate the asymptotic exponential growth rate of B(n, d, w) with respect to n and with fixed ratios δ = d/n and ω = w/n. For ω ∈ [0, 1/2], this growth rate function b(δ, ω) is shown to be equal to a(δ), the asymptotic exponential growth rate of A(n, d)-the maximum number of length n binary sequences with minimum distance d. For ω ∈ (1/2, 1), we show that b(δ, ω) ≤ a(δ, ω) + f(ω), where a(δ, ω) denotes the asymptotic exponential growth rate of A(n, d, w), the maximum number of length n binary sequences with minimum distance d and constant weight w, and where f(w) is a certain function that satisfies 0ω→1f(ω) = limω→1/2f(ω) = 0. Based on numerical evidence, we conjecture that b(δ, ω) is actually equal to a(δ, ω) for ω ∈ (1/2, 1). Finally, lower bounds on B(n, d, w) are obtained via explicit code constructions.

Starting from a practical use of Reed-Solomon codes in a cryptographic scheme published in Indocrypt'09, this paper deals with the threshold of linear q-ary error-correcting codes. The security of this scheme is based on the intractability of polynomial reconstruction when there is too much noise in the vector. Our approach switches from this paradigm to an Information Theoretical point of view: is there a class of elements that are so far away from the code that the list size is always superpolynomial? Or, dually speaking, is Maximum-Likelihood decoding almost surely impossible? We relate this issue to the decoding threshold of a code, and show that when the minimal distance of the code is high enough, the threshold effect is very sharp. In a second part, we explicit lower-bounds on the threshold of Maximum-Distance Separable codes such as Reed-Solomon codes, and compute the threshold for the toy example that motivates this study.

Identification codes were introduced by Ahlswede and Dueck more than twenty years ago. There is today a lot of studies to identify objects such as contactless devices (for instance RFID tags) but, surprisingly, no one has considered the use of this kind of codes in the literature for that purpose until the recent work of Bringer et al. at Indocrypt '09. We here show how the security of these new identification protocols is related to some well-known problems in coding theory. We also extend the original proposal to a new problem.

Körner and Malvenuto asked whether one can find $\binom{n}{\lfloor n/2\rfloor}$ linear orderings (i.e., permutations) of the first n natural numbers such that any pair of them places two consecutive integers somewhere in the same position. This led to the notion of graph-different permutations. We extend this concept to directed graphs, focusing on orientations of the semi-infinite path whose edges connect consecutive natural numbers. Our main result shows that the maximum number of permutations satisfying all the pairwise conditions associated with all of the various orientations of this path is exponentially smaller, for any single orientation, than the maximum number of those permutations which satisfy the corresponding pairwise relationship. This is in sharp contrast to a result of Gargano, Körner, and Vaccaro concerning the analogous notion of Sperner capacity of families of finite graphs. We improve the exponential lower bound for the original problem and list a number of open questions.

We propose an original technique for the design of convolutional Tanner structures that are full diversity under iterative decoding. The code design is based on the analysis of the local trellis neighborhood and is suitable for transmission over wireless non-ergodic channels. This new technique enables us to split the giant convolutional checknode into multiple smaller checknodes which is a means to mimic the standard analysis of LDPC codes under iterative message passing decoding.

Fuzzy commitment schemes, introduced as a link between biometrics and cryptography, are a way to handle biometric data matching as an error-correction issue. We focus here on finding the best error-correcting code with respect to a given database of biometric data. We propose a method that models discrepancies between biometric measurements as an erasure and error channel, and we estimate its capacity. We then show that two-dimensional iterative min-sum decoding of properly chosen product codes almost reaches the capacity of this channel. This leads to practical fuzzy commitment schemes that are close to theoretical limits. We test our techniques on public iris and fingerprint databases and validate our findings.

We investigate the packing and covering densities of linear and nonlinear binary codes, and establish a number of duality relationships between the packing and covering problems. Specifically, we prove that if almost all codes are good packings, then only a vanishing fraction of codes are good coverings, and vice versa: if almost all codes are good coverings, then at most a vanishing fraction of codes are good packings. We also show that any specific maximal binary code is either a good packing or a good covering, in a certain well-defined sense.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis, we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg, and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

We treat the problem of bounding components of the possible distance distributions of codes given the knowledge of their size and possibly minimum distance. Using the Beckner inequality from harmonic analysis we derive upper bounds on distance distribution components which are sometimes better than earlier ones due to Ashikhmin, Barg and Litsyn. We use an alternative approach to derive upper bounds on distance distributions in linear codes. As an application of the suggested estimates we get an upper bound on the undetected error probability for an arbitrary code of given size. We also use the new bounds to derive better upper estimates on the covering radius, as well as a lower bound on the error-probability threshold, as a function of the code's size and minimum distance.

The combinatorial concept of separating systems has numerous applications, such as automata theory, digital fingerprinting, group testing, and hashing. In this correspondence, we derive upper bounds on the size of codes with various separating properties.

We find the rate of a typical code from the regular low-density parity-check (LDPC) ensemble. We then show that the rate of a code from the ensemble converges to the design rate in quadratic mean and almost surely.

The theory of separating systems has been applied in different areas of science and technology such as automata synthesis, technical diagnosis, and authenticating ownership claims. Constructions of (2,2)-separating systems derived from error-correcting codes are given, together with bounds on their parameters based on distance considerations.

Let C be a code of length n over an alphabet of q letters. An n-word y is called a descendant of a set of t codewords x 1 , . . . ,x t if $y_i\in\{x^1_i,\dots,x^t_i\}$ for all i=1, . . . ,n. A code is said to have the t-identifying parent property if for any n-word that is a descendant of at most t parents it is possible to identify at least one of them. We prove that for any $t\le q-1$ there exist sequences of such codes with asymptotically nonvanishing rate.

Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v)/spl cap/C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)/spl cap/C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.

In an undirected graph G=(V,E), a subset $C \subseteq V$ is called an identifying code if the sets $B_1(v) \cap C$ consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.

We improve estimates on the parameters of quantum codes obtained by Steane's (see ibid., vol.45, no.7, p.2492-5, 1999) construction from binary codes. This yields several new families of quantum codes.

New constructions of binary linear intersecting codes are presented. Some codes with high distances are shown to be intersecting.

We study geometrically the domain of linear binary codes and of unrestricted binary codes in the plane (normalized covering radius, normalized minimal distance).

We study partitions of the space $\mathbb{F}_2^n $ of all the binary n-tuples into disjoint sets, where each set is an additive cosec of a given set V. Such a partition is called a tiling of $\mathbb{F}_2^n $ and denoted $(V,A)$, where A is the set of cosec representatives. We give a sufficient condition for a set V to be a tile in terms of the cardinality of $V + V$. We then employ this condition to classify all tilings with sets of small cardinality. Further, periodicity of tilings in $\mathbb{F}_2^n $ is discussed, and a simple construction of nonperiodic tilings of $\mathbb{F}_2^n $ is presented for all $n \geq 6$. It is also shown that the nonperiodic tiling of $\mathbb{F}_2^6 $ is unique. A tiling $(V,A)$ is said to be proper if V generates $\mathbb{F}_2^n $; it is said to be full rank if both V and A generate $\mathbb{F}_2^n $. We show that, in general, the classification of tilings can be reduced to the study of proper tilings. We then prove that any tiling may be decomposed into smaller tilings that are either trivial or have full rank. Existence of full-rank tilings is exhibited by showing that each tiling is uniquely associated with a perfect binary code. Moreover, it is shown that periodic full-rank tilings may be further decomposed into smaller tilings, and then the existence of nonperiodic full-rank tilings is deduced. Finally, we generalize the well-known Lloyd theorem, originally stated for tilings by spheres, for the case of arbitrary tilings.

Given a subset X of vertices of the n-cube (i.e., the n-dimensional Hamming space), we are interested in the solution of the traveling salesman problem; namely, the minimal length of a cycle passing through all vertices of X. For a given number M, we estimate the maximum of these lengths when X ranges over all possible choices of sets of M vertices. Asymptotically, our estimates show that for a number M of vertices growing exponentially in n, the maximum is attained for a code with maximal possible minimum distance.

We study a wide class of problems in coding theory for which we consider two different formulations: in terms of incidence matrices and in terms of hypergraphs. These problems are dealt with using a greedy algorithm due to Stein (1974) and Lovasz (1975). Some examples, including constructing covering codes, codes for conflict resolution, separating systems, source encoding with distortion, etc., are given a unified treatment. Under certain conditions derandomization can be performed, leading to an essential reduction in the complexity of the constructions.

Introduces a generalization of the concepts of coverings and packings in Hamming space called weighted coverings and packings. This allows to formulate a number of well-known coding theoretical problems in a uniform manner. The authors study the existence of perfect weighted codes, discuss connections between weighted coverings and packings, and present many constructions for them.

We define and estimate the threshold probability /spl theta/ of a linear code, using a theorem of Margulis (1974) originally conceived for the study of the probability of disconnecting a graph. We then apply this concept to the study of the erasure and Z-channels, for which we propose linear coding schemes that admit simple decoding. We show that /spl theta/ is particularly relevant to the erasure channel since linear codes achieve a vanishing error probability as long as p/spl lesspl theta/, where p is the probability of erasure. In effect, /spl theta/ can be thought of as a capacity notion designed for codes rather than for channels. Binomial codes haven the highest possible /spl theta/ (and achieve capacity). As for the Z-channel, a subcapacity is derived with respect to the linear coding scheme. For a transition probability in the range ]log (3/2); 1[, we show how to achieve this subcapacity. As a by-product we obtain improved constructions and existential results for intersecting codes (linear Sperner families) which are used in our coding schemes.>

We derive new asymptotic bounds for generalized distances. Our approach extends the classical Hamming, Plotkin, and Elias bounds. The latter bound involves extending the definition of generalized distances to nonlinear codes.>

A binary intersecting code is a linear code with the property that any two nonzero codewords have intersecting supports. These codes appear in a wide variety of contexts and applications, e.g., multiple access, cryptography, and information theory. This paper is devoted partly to the study of intersecting codes, and partly to their use in constructing large t-independent families of binary vectors. The latter subject has by now been extensively studied and has application in VLSI testing, defect correction, E-biased probability spaces, and derandomization. By concatenation methods we construct codes with the highest known fate asymptotically. We then generalize the concept to t-wise intersecting codes: we give bounds on the achievable rate of such codes, both existential and constructive. We show how t-wise intersecting codes can be used to obtain (t+1)-independent families. With this method we obtain improved asymptotical constructions of t-independent families. Complexity issues are discussed.>

The authors investigate the problem of evaluating the possible size of error-correcting codes with code words taken from a subset of Hamming spaces. This is an example of the problem of constructing codes in irregular subsets of Hamming spaces. The authors examine the theoretical restrictions on the parameters of error-correcting codes in the asymptotic case (semi-finite sequence) when the recursive digital sum is upper-bounded by some small constant. The bounds allow demonstration of the existence of long codes that have good error-correcting properties and that satisfy some restrictions that are natural for optical and magnetic recording.>

Let Q be an alphabet of size q>or=2. The Hamming space Q/sup n/ that consists of all n-tuples of elements of Q is a metric space, provided with the Hamming distance function. A perfect multiple covering (PMC) is a code C in Q/sup n/ such that there exist fixed numbers r and mu with the property that every word in Q/sup n/ is within distance r from exactly mu codewords of C. The authors give a few constructions of PMCs and investigate in detail the problem of determining all possible parameters of PMCs with r=1.>

A problem raised by R.L. Rivest and A. Shamir (1982), namely, constructing write-once-memory (WOM) codes capable of error correction, is considered. The authors call a (n,m,t)-WOM code a scheme that allows t successive writings of m arbitrary bits (i.e., one message among 2/sup m/) on a WOM of size n. WOM codes have been studied from an information-theoretic viewpoint by J.K. Wolf et al. (1984) and constructed using classical coding theory by G.D. Cohen et al. (1986, 1987) (for example, with parameters, (23,11,3), (2/sup m-1/,m,2/sup m-2/+2/sup m-4/+1)). The authors adapt those methods in order to solve the problem raised by Rivest. Large classes of easily decodable single-error-correcting WOM codes are obtained.>

A new vector coding (quantization) system and its application to speech waveforms are presented. This system consists of several permutation codes of Variant I. An algorithm for the system design is developed. An encoding procedure which minimizes the distortion and finds out the reproduction index to be transmitted using a algebraic method is proposed. The system was designed and tested for the encoding of speech waveforms. The results of experimental simulations show that this is a prospective vector coding scheme with simple encoding procedure, smaller memory required, and not large computational burden of the design algorithm.

An application of error-correcting codes to "write-once" memories (WOM's) as defined by Rivest and Shamir is studied. Large classes of "WOM codes" that are easily decodable are obtained. In particular, a construction allowing three successive writings of11bits on23positions is derived from the Golay code.

A number of upper and lower bounds are obtained forK(n, R), the minimal number of codewords in any binary code of lengthnand covering radiusR. Several new constructions are used to derive the upper bounds, including an amalgamated direct sum construction for nonlinear codes. This construction works best when applied to normal codes, and we give some new and stronger conditions which imply that a linear code is normal. An upper bound is given for the density of a covering code over any alphabet, and it is shown thatK(n + 2, R + 1) \leq K(n, R)holds for sufficiently largen.

All known results on covering radius are presented, as well as some new results. There are a number of upper and lower bounds, including asymptotic results, a few exact determinations of covering radius, some extensive relations with other aspects of coding theory through the Reed-Muller codes, and new results on the least covering radius of any linear[n,k]code. There is also a recent result on the complexity of computing the covering radius.

Lett(n,k)denote the minimum covering radius of a binary linear(n,k)code. We give a nonconstructive upper bound ont(n,k), which coincides asymptotically with the known lower bound, namelyn^{-1}t(n,nR)=H^{-1}(1-R)+O(n^{-l}\log n), whereRis fixed,0<R<1, andH^{-1}is the inverse of the binary entropy function.

Some new examples of binary Bose-Chaudhuri-Hocquanghen (BCH) codes of length 255 are found for which the minimum distance and designed distance agree.

Transposing a computation of Mac Williams we derive an exact expression for, and a straightforward upper bound on, the residual error rate of a binary block code with a "standard" decoder. We also give series expansions for decoding error probability and residual error rates.