Theory Lunch Seminar

  • CHRIS COX
  • Ph.D. Student, Program in Algorithms, Combinatorics and Optimization
  • Department of Mathematics
  • Carnegie Mellon University
Seminars

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.

For More Information, Please Contact: 
Keywords: