  In this work, we study the trade-off between the running time of
approximation algorithms and their approximation guarantees. By leveraging a
structure of the `hard' instances of the Arora-Rao-Vazirani lemma [JACM'09], we
show that the Sum-of-Squares hierarchy can be adapted to provide `fast', but
still exponential time, approximation algorithms for several problems in the
regime where they are believed to be NP-hard. Specifically, our framework
yields the following algorithms; here $n$ denote the number of vertices of the
graph and $r$ can be any positive real number greater than 1 (possibly
depending on $n$).
  (i) A $\left(2 - \frac{1}{O(r)}\right)$-approximation algorithm for Vertex
Cover that runs in $\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time.
  (ii) An $O(r)$-approximation algorithms for Uniform Sparsest Cut, Balanced
Separator, Minimum UnCut and Minimum 2CNF Deletion that runs in
$\exp\left(\frac{n}{2^{r^2}}\right)n^{O(1)}$ time.
  Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm
[arXiv:1708.03515] which achieves $\left(2 -
\frac{1}{O(r)}\right)$-approximation in time
$\exp\left(\frac{n}{r^r}\right)n^{O(1)}$. For the remaining problems, our
algorithms improve upon $O(r)$-approximation
$\exp\left(\frac{n}{2^r}\right)n^{O(1)}$-time algorithms that follow from a
work of Charikar et al. [SIAM J. Comput.'10].
