We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approximation scheme, unless NP-complete problems can be solved in randomized subexponential time. Furthermore, we show that the same techniques can be used for the Maximum Edge Biclique problem, for which we obtain a hardness factor similar to previous results but under a more standard assumption. Copyright © by SIAM.