Existing video streaming algorithms use various estimation approaches to infer the inherently variable bandwidth in cel- lular networks, which often leads to reduced quality of expe- rience (QoE). We ask the question: \If accurate bandwidth prediction were possible in a cellular network, how much can we improve video QoE?". Assuming we know the bandwidth for the entire video session, we show that existing stream- ing algorithms only achieve between 69%-86% of optimal quality. Since such knowledge may be impractical, we study algorithms that know the available bandwidth for a few sec- onds into the future. We observe that prediction alone is not sufficient and can in fact lead to degraded QoE. However, when combined with rate stabilization functions, prediction outperforms existing algorithms and reduces the gap with optimal to 4%. Our results lead us to believe that cellular operators and content providers can tremendously improve video QoE by predicting available bandwidth and sharing it through APIs.