A (v, k, λ)-difference set in a groupGof ordervis a subset {d1,d2, . . . ,dk} ofGsuch thatD= Σdiin the group ring Z[G] satisfiesDD−1=n+ λG, wheren = k− λ. In other words, the nonzero elements ofGall occur exactly λ times as differences of elements inD. A (v, k, λ, t)-almost difference set has t nonzero elements ofGoccurring λ times, and the otherv− 1 −toccurring λ + 1 times. When λ = 0, this is equivalent to a modular Golomb ruler. In this paper we investigate existence questions on these objects, and extend previous results constructing almost difference sets by adding or removing an element from a difference set. We also show for which primes the octic residues, with or without zero, form an almost difference set.

One way to find near-matches in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given; for the Hamming metric projecting onto$k$bits is simple hash function that performs well. In this paper, we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for error-correcting codes work better, and asymptotically random codes perform better than projection.

Delsarte conjectured in 1973 that there are no nontrivial pefect codes in the Johnson scheme. Etzion and Schwartz recently showed that perfect codes must be k-regular for large k, and used this to show that there are no perfect codes correcting single errors in J(n,w) for n les 50 000. In this correspondence we show that there are no perfect single error-correcting codes for n les 2250

Let A(n,d) denote the greatest number of codewords possible in a binary block code of length n and distance d. Plotkin gave a simple counting argument which leads to an upper bound B(n,d) for A(n,d) when d>n/2. Levenshtein (1964) proved that if Hadamard's conjecture is true then Plotkin's bound is sharp. Though Hadamard's conjecture is probably true, its resolution remains a difficult open question. So it is natural to ask what one can prove about the ratio R(n,d)=A(n,d)/B(n,d). This note presents an efficient heuristic for constructing, for any d/spl ges/n/2, a binary code which has at least 0.495B(n,d) codewords. A computer calculation confirms that R(n,d)>0.495 for d up to one trillion.

Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c + o ( 1 ) ) ( \log n )^v ( \log \log n )^{1 - v } \right\} \] for $n \to \infty $. This paper presents an algorithm to solve the discrete logarithm problem for $GF ( p )$ with heuristic expected running time $L_p [ 1/3; 3^{2/3}]$. For umbers of a special form, there is an asymptotically slower but more practical version of the algorithm.

For permutation decoding of aneerror-correcting linear code, a set of permutations which move all error vectors of weight\leq eout of the information places is needed. A method of finding minimal decoding sets is given, along with minimal sets obtained with this method for the binary Golay codes.