期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
