We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. In all cases, the sizes of the objects ar e optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen such object has the required properties with positive yet tiny pr obability. The main technical ingredient is a special local central limit theorem for suitable lattice ra ndom walks with finitely many steps.
Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal. This paper gives a new method for reducing the size of families given by previous constructions. Our method relies on pseudorandom generators for space-bounded computations. In fact, all we need is a generator, that produces “pseudorandom walks” on undirected graphs with a consistent labelling. One such generator is implied by Reingold's log-space algorithm for undirected connectivity [21,22]. We obtain families of k-wise almost independent permutations, with an optimal description length, up to a constant factor. More precisely, if the distance from uniform for any k tuple should be at most δ, then the size of the description of a permutation in the family is @math . We construct an explicit generating sets @math and @math of the alternating and the symmetric groups, which make the Cayley graphs @math and @math a family of bounded degree expanders for all sufficiently large @math . These expanders have many applications in the theory of random walks on groups and other areas of mathematics.