We show that for k \geq 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k\geq 5, there is a strictly increasing function f: [0,1] \rightarrow \mathbb{R} with f(0) = 0 that has the following property. If F is a k-CNF formula over n variables and |{\rm sat}(F)| = 2^{\delta n} solutions, then PPSZ finds a satisfying assignment with probability at least 2^{-c_k n -o(n) + f(\delta) n}. Here, 2^{-c_k n - o(n)} is the success probability proved by Paturi, Pudlak, Saks, and Zane for k-CNF formulas with a unique satisfying assignment.

Our proof rests on a combinatorial lemma: given a set S \subseteq \{0,1\}^n, we can partition \{0,1\}^n into subcubes such that each subcube B contains exactly one element of S. Such a partition \mathcal{B} induces a distribution on itself, via \Pr[B] = |B| / 2^n for each B \in \mathcal{B}. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (\min_{S: |S| = s} \max_{\mathcal{B}} H(\mathcal{B})) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.