  The recent observation of high-energy astrophysical neutrinos can be used to
constrain violations of Lorentz invariance emerging from a quantum theory of
gravity. We perform threshold and Cherenkov analyses that improve existing
bounds by factors ranging from about a million to 10^{20}.
