  In this paper, we develop new tools and connections for exponential time
approximation. In this setting, we are given a problem instance and a parameter
$\alpha>1$, and the goal is to design an $\alpha$-approximation algorithm with
the fastest possible running time. We show the following results:
  - An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r
\log^2 r+r\log^2r)))$ time,
  - An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log
r+r\log^2r)))$ time,
  - A $(2-1/r)$-approximation for minimum vertex cover in
$O^*(\exp(n/r^{\Omega(r)}))$ time, and
  - A $(k-1/r)$-approximation for minimum $k$-hypergraph vertex cover in
$O^*(\exp(n/(kr)^{\Omega(kr)}))$ time.
  (Throughout, $\tilde O$ and $O^*$ omit $\mathrm{polyloglog}(r)$ and factors
polynomial in the input size, respectively.) The best known time bounds for all
problems were $O^*(2^{n/r})$ [Bourgeois et al. 2009, 2011 & Cygan et al. 2008].
For maximum independent set and chromatic number, these bounds were
complemented by $\exp(n^{1-o(1)}/r^{1+o(1)})$ lower bounds (under the
Exponential Time Hypothesis (ETH)) [Chalermsook et al., 2013 & Laekhanukit,
2014 (Ph.D. Thesis)]. Our results show that the naturally-looking
$O^*(2^{n/r})$ bounds are not tight for all these problems. The key to these
algorithmic results is a sparsification procedure, allowing the use of better
approximation algorithms for bounded degree graphs. For obtaining the first two
results, we introduce a new randomized branching rule.
  Finally, we show a connection between PCP parameters and exponential-time
approximation algorithms. This connection together with our independent set
algorithm refute the possibility to overly reduce the size of Chan's PCP [Chan,
2016]. It also implies that a (significant) improvement over our result will
refute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].
