What Can and What Cannot Be Done by LP and SDP (An Incomplete Overview)

In celebration of Alexander Barg’s Hamming Award.

Delsarte's linear programming method was initially proposed for bounding the size of the largest possible binary codes. In short order, it gave rise to the MRRW bound (1978), which remains the best-known asymptotic estimate of the largest rate of binary codes. For finite parameters, the MRRW bound was improved by Levenshtein. In the 1970s, this method was also extended first to spherical codes and then to a broad class of metric spaces that admit distance-transitive group actions. Simultaneously, concepts highlighted by this method resulted in many links to combinatorial objects such as few-distance sets, equiangular lines, strongly regular graphs, and tight frames. Following this, three-(and more)-point bounds for codes emerged, with notable highlights including new bounds for kissing numbers, sphere packings, and bounds for energy of codes.

The talk will provide a partial (and biased) overview of some of these results and connections. We will give quick proofs of the MRRW and Levenshtein bounds that require no calculations, while serving as a segue to the Cohn-Elkies bound for sphere packings. Additionally, we will mention recent results on equiangular lines, codes with few distances, energy bounds for codes, and links to smoothing of codes and uniform distributions.