The trace-norm has received much attention in the context of matrix recovery and has also been used for other learning tasks. In this talk, I will focus on an alternative, the so-called max-norm (or gamma_2:l_1->l_inf norm), which, like the trace-norm, can also be viewed as a matrix factorization norm, and is strongly related to the SDP relaxation used in many approximation algorithms involving cuts. I will show how the max-norm is a better surrogate for the rank, present recent results on exact cluster recovery using the max-norm, and discuss other problems where it could be relevant, attempting to highlight the connection between the learning work that lead to the use of the max-norm, and its use and study in the context of SDP relaxations by the theory -of-computation community.