  Restarts are a widely-used class of techniques integral to the efficiency of
Conflict-Driven Clause Learning (CDCL) Boolean SAT solvers. While the utility
of such policies has been well-established empirically, a theoretical
explanation of whether restarts are indeed crucial to the power of CDCL solvers
is lacking. In this paper, we prove a series of theoretical results that
characterize the power of restarts for various models of SAT solvers. More
precisely, we make the following contributions. First, we prove an exponential
separation between a {\it drunk} randomized CDCL solver model with restarts and
the same model without restarts using a family of satisfiable instances.
Second, we show that the configuration of CDCL solver with VSIDS branching and
restarts (with activities erased after restarts) is exponentially more powerful
than the same configuration without restarts for a family of unsatisfiable
instances. To the best of our knowledge, these are the first separation results
involving restarts in the context of SAT solvers. Third, we show that restarts
do not add any proof complexity-theoretic power vis-a-vis a number of models of
CDCL and DPLL solvers with non-deterministic static variable and value
selection.
