Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-144 | 2nd November 2011 14:48

Probabilistic existence of rigid combinatorial structures

RSS-Feed




TR11-144
Authors: Greg Kuperberg, Shachar Lovett, Ron Peled
Publication: 2nd November 2011 21:25
Downloads: 1254
Keywords: 


Abstract:

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 are 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 probability. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.



ISSN 1433-8092 | Imprint