  We give a new general approach for designing exact exponential-time
algorithms for subset problems. In a subset problem the input implicitly
describes a family of sets over a universe of size n and the task is to
determine whether the family contains at least one set. Our approach is based
on "monotone local search", where the goal is to extend a partial solution to a
solution by adding as few elements as possible. More formally, in the extension
problem we are also given as input a subset X of the universe and an integer k.
The task is to determine whether one can add at most k elements to X to obtain
a set in the (implicitly defined) family. Our main result is that an O*(c^k)
time algorithm for the extension problem immediately yields a randomized
algorithm for finding a solution of any size with running time O*((2-1/c)^n).
  In many cases, the extension problem can be reduced to simply finding a
solution of size at most k. Furthermore, efficient algorithms for finding small
solutions have been extensively studied in the field of parameterized
algorithms. Directly applying these algorithms, our theorem yields in one
stroke significant improvements over the best known exponential-time algorithms
for several well-studied problems, including d-Hitting Set, Feedback Vertex
Set, Node Unique Label Cover, and Weighted d-SAT. Our results demonstrate an
interesting and very concrete connection between parameterized algorithms and
exact exponential-time algorithms.
  We also show how to derandomize our algorithms at the cost of a
subexponential multiplicative factor in the running time. Our derandomization
is based on an efficient construction of a new pseudo-random object that might
be of independent interest. Finally, we extend our methods to establish new
combinatorial upper bounds and develop enumeration algorithms.
