Clark School Home UMD
Return to Research Awards

NSF Collaborative Research: Multivariate positive definite polynomials and their applications via SDP

Faculty 

Funding Agency 

National Science Foundation

Description 

This project is devoted to the study of point allocations on the real sphere and related configurations using methods of distance geometry, coding theory, and semidefinite programming.  The properties of the point sets studied include restricting the minimum angular separation between any pair of distinct points in the set or the degree of the cubature formula supported by it.  Recent advances in these problems include a solution by the investigator of the kissing number problem in 4 dimensions, a new proof for the kissing number problem in 3 dimensions, and a new approach to bounds on codes using semidefinite programming, due to Schrijver, Bachoc, and the investigator. The kissing problem in x dimensions is the question of how many unit spheres can touch (kiss) a unit sphere in x dimensions. The new ideas developed in these works pave the way for further advances in the problems of bounding the size of codes and in a number of other problems in distance geometry.  The main problems to be addressed in the project are related to bounding the size of optimal sets of points on a sphere when the sets have a certain property, and the links between the bounding problem and multivariate positive definite polynomials.  Interesting properties of the point set include having a minimum angular separation that exceeds a given value between any two points in the set (this is relevant for signal processing problems), and supporting an exact cubature formula for spherical harmonic functions of a given degree. Applications of the point sets studied include communication theory, numerical analysis, the meshing problem, data representation, and localization in sensor networks.

Multivariate positive definite polynomials and their applications via SDP is a thre-year, $114K grant.