Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-120 | 27th July 2010 02:02

Lower bounds for designs in symmetric spaces


Authors: Noa Eidelstein, Alex Samorodnitsky
Publication: 27th July 2010 17:25
Downloads: 3089


A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube.

We prove lower bounds on designs in spaces with a large group of symmetries. These spaces include globally symmetric Riemannian spaces (of any rank) and commutative association schemes with $1$-transitive group of symmetries.

Our bounds are, in general, implicit, relying on estimates on the spectral behavior of certain symmetry-invariant linear operators.
They reduce to the first linear programming bound for designs in globally symmetric Riemannian spaces of rank-$1$ or in distance regular graphs. The proofs are different though, coming from viewpoint of abstract harmonic analysis in symmetric spaces. As a dividend we obtain the following geometric fact: a design is large because a union of "spherical caps" around its points "covers" the whole space.

ISSN 1433-8092 | Imprint