Many concurrency platforms offer a processor oblivious model of computation, where the scheduler dynamically distributes work across threads. While this is convenient, it introduces non\hyp determinism at runtime, which complicates debugging, since it precludes repeatability. Leiserson et al. [PPoPP '12] persuaded Intel to modify its C/C++ compiler, which provided the Cilk Plus concurrency platform, to include a feature called pedigrees, which enables determinism by uniquely identifying strands with low overhead. They used pedigrees to design a DPRNG called DOTMIX, which hashes a pedigree, then mixes the result into a random number for a given strand. Improving the efficiency of DOTMIX by using a faster hash function is an open problem put forth by Leiserson et al. [PPoPP '12]. We address this problem and improve the speed of the algorithm roughly by a factor of two, without sacrificing any statistical quality. Specifically, we replace the compression function used in DOTMIX with a faster universal hash function family due to Etzel et al. [CRYPTO '99] called Square Hash.

We introduce a general class of codes which includes several well-known classes of deletion/insertion correcting codes as special cases. For example, the Helberg code, the Levenshtein code, the Varshamov-Tenengolts code, and most variants of these codes including most of those which have been recently used in studying DNA-based data storage systems are all special cases of our code. Then, using a number theoretic method, we give an explicit formula for the weight enumerator of our code which in turn gives explicit formulas for the weight enumerators and for the sizes of all the aforementioned codes. We also obtain the size of the shifted Varshamov-Tenengolts code. Another application which automatically follows from our result is an explicit formula for the number of binary solutions of an arbitrary linear congruence which, to the best of our knowledge, is the first result of its kind in the literature and might be also of independent interest. Our general result might have more applications/implications in information theory, computer science, and mathematics.

We derive an explicit expression for the weight enumerator of a general class of codes which includes several classes of deletion correcting codes, such as Helberg, Levenshtein, and Shifted Varshamov- Tenengolts codes, as special cases. Our approach generalizes the number-theoretic methods previously used for evaluating the size of single deletion correcting codes, and also leads to a new explicit formula for the number of binary solutions of an arbitrary linear congruence which might be also of independent interest.

Let Zn[i] be the ring of Gaussian integers modulo a positive integer n. Very recently, Camarero and Martinez et al. showed that for every prime number p > 5 such that p ≡ ±5 (mod 12), the Cayley graph ςp= Cay(Zp[i], S2), where S2is the set of units of Zp[i], induces a two-quasi-perfect Lee code over Zpm, where m = 2[p/4]. They also conjectured that ςpis a Ramanujan graph for every prime p, such that p ≡ 3 (mod 4). In this paper, we solve this conjecture. Our main tools are Deligne's bound from 1977 for estimating a particular kind of trigonometric sum and a result of Lovász from 1975 (or of Babai from 1979) which gives the eigenvalues of Cayley graphs of finite Abelian groups. Our proof techniques may motivate more work in the interactions between spectral graph theory, character theory, and coding theory, and may provide new ideas toward the famous Golomb-Welch conjecture on the existence of perfect Lee codes.