  The worst-case fastest known algorithm for the Set Cover problem on universes
with $n$ elements still essentially is the simple $O^*(2^n)$-time dynamic
programming algorithm, and no non-trivial consequences of an $O^*(1.01^n)$-time
algorithm are known. Motivated by this chasm, we study the following natural
question: Which instances of Set Cover can we solve faster than the simple
dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm
that determines the existence of a set cover of size $\sigma n$ in
$O^*(2^{(1-\Omega(\sigma^4))n})$ time. Our approach is also applicable to Set
Cover instances with exponentially many sets: By reducing the task of finding
the chromatic number $\chi(G)$ of a given $n$-vertex graph $G$ to Set Cover in
the natural way, we show there is an $O^*(2^{(1-\Omega(\sigma^4))n})$-time
randomized algorithm that given integer $s=\sigma n$, outputs NO if $\chi(G) >
s$ and YES with constant probability if $\chi(G)\leq s-1$.
  On a high level, our results are inspired by the `representation method' of
Howgrave-Graham and Joux~[EUROCRYPT'10] and obtained by only evaluating a
randomly sampled subset of the table entries of a dynamic programming
algorithm.
