Greg Kuperberg

If a finite set S densely generates a compact, semisimple Lie group G, then how well does the set of words of length ℓ in S (and S^-1) approximate G?   The words of length ℓ could be an ε-net of G; or they could be evenly distributed down to a scale of ε; or there could be an algorithm to produce a word that lies within ε of any given g ∈ G.  An optimal statistical result, with ℓ = O(log 1/ε), was first established by Lubotzky, Phillips, and Sarnak when G = SU(2) for special choices of S; and later generalized by others, but still with some restrictions on S. Independently, in the field of quantum computing, Solovay and Kitaev established an algorithm to find a word with ℓ = O((log 1/ε)^α) for any S and (initially) also G = SU(2).   I will discuss the current status of different versions of this question, including versions when G might not be compact or S^-1 might not be used.  I will also discuss my own result, in which I improve the exponent in the (algorithmic) Solovay-Kitaev theorem from the previous best value of α = 3+δ to α = (log_ϕ 2) + δ < 1.4405.