Theory Lunch Seminar

Wednesday, October 17, 2018 - 12:00pm to 1:00pm


8102 Gates Hillman Centers


CHRIS COX, Ph.D. Student, Program in Algorithms, Combinatorics and Optimization

Small Antipodal Spherical Codes

Speaker: Chris Cox

Location: GHC 8102

Small Antipodal Spherical Codes

An antipodal spherical ε-code in ℝ^d is a collection of vectors X ⊆ S^(d-1) for which |〈x,y〉| ≤ ε for all x≠y∈X. Such codes can be viewed as a generalization of Hamming codes in F_2^d where all distances lie within [1/2*(1-ε)*d,1/2*(1+ε)*d]. In this talk, we'll be interested in the parameter θ(d,k), which is the smallest ε for which there is an antipodal spherical ε-code in ℝ^d with d+k vectors. In other words, θ(d,k) is the answer to the question "how can d+k vectors in R^d be arranged so that they are as close to orthogonal as possible?" We focus on the case when k is fixed and d→∞, that is, when the code has a small excess number of vectors compared to the dimension. We find an intimate relationship between determining θ(d,k) and the existence of (k+1 choose 2) equiangular lines in ℝ^k; thus, we are able to pin down θ(d,k) precisely for k ∈ {0,1,2,3,7,23} and establish asymptotics for general k. Usually when studying spherical codes, one uses linear programming techniques, but the main tool in our result is instead a tight upper bound on E_{x, y~μ}|〈x,y〉| whenever μ is an isotropic probability mass on ℝ^k, which may be of independent interest. Our results translate naturally to the analogous question in ℂ^d, in which case the question relates to the existence of k^2 equiangular lines in ℂ^k, also known as SIC-POVM in physics literature.

Joint work with Boris Bukh.

View post-lecture videos at CMU Youtube Theory channel.

Event Website:,%202018.html

For More Information, Contact:


Seminar Series