The IceCube neutrino observatory has measured the TeV-scale atmospheric neutrino flux with increasing accuracy. As statistics accumulate, corresponding improvements in treatments of systematic uncertainty enable highly sensitive searches for beyond Standard Model physics. In this poster, I will highlight our recent searches for Lorentz Violation and sterile neutrinos using high-energy muon neutrinos. The first is uniquely enhanced by the high neutrino energies in the IceCube sample, and the second by possible enhancements in the active-to-sterile oscillation probabilities due to matter effects.