I am trying to understand PPZ (Paturi, Pudlák, Zane) derandomization algorithm for k-SAT, it seems to be very difficult for me. The last line in the below of the image, I don't understand the time complexity.

My question is how to get at most $\widetilde{O}(2^{n(1−c_k)})$ time for $c_k = \frac{1}{2k} − o(\frac{1}{2})$, where the asymptotics in $o(. . .)$ is when $k\to\infty$?

enter image description here

Details of the note is here. Above image is 1.3 section of this PDF.


1 Answer 1


$\let\ep\varepsilon$Note that the stated estimate $\tilde O\bigl(2^{H(\ep)n}\bigr)$ on the volume of the Hamming ball only holds for $\ep\le1/2$ (for $\ep\ge1/2$, it stays $\Theta(2^n)$). As the paper says, in order to optimize the sum, a good choice is $\ep\le1/2$ such that $H(\ep)=1-\ep/k$.

For $k$ large, this is close to $1$, and $H(\ep)$ is close to $1$ for $\ep$ close to $1/2$. Thus, write $\ep=\frac12(1-\delta)$, $\delta\ge0$, and compute the asymptotics of $H(\ep)$ for small $\delta$: $$\begin{align*} H(\ep)&=\ep\bigl(1-\log(1-\delta)\bigr)+(1-\ep)\bigl(1-\log(1+\delta)\bigr)\\ &=1+\ep\bigl(\delta+\tfrac12\delta^2+O(\delta^3)\bigr)\log e+(1-\ep)\bigl(-\delta+\tfrac12\delta^2+O(\delta^3)\bigr)\log e\\ &=1-(1-2\ep)\delta\log e+\tfrac12\delta^2\log e+O(\delta^3)\\ &=1-\frac{\log e}2\delta^2+O(\delta^3). \end{align*}$$ The equation $H(\ep)=1-\ep/k$ becomes $$1-\frac{\log e}2\delta^2(1+O(\delta))=1-\frac1{2k}(1+O(\delta)),$$ thus $\delta=\frac1{\sqrt{k\log e}}(1+O(\delta))$, which solves to $$\delta=\frac1{\sqrt{k\log e}}+O(k^{-1}).$$ Plugging this back, $\ep$ satisfies $$H(\ep)=1-\frac\ep k=1-\frac1{2k}+\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$ So, we get $$c_k=\frac1{2k}-\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$

  • 1
    $\begingroup$ I’m not sure I understand your comment. This is the asymptotic expansion of $\log(1-\delta)$ up to $O(\delta^3)$; I could have used more terms to get a more precise estimate, but this is enough for the basic bound on $c_k$. $\endgroup$ Jan 26 at 12:56
  • 1
    $\begingroup$ You write, $$1-\frac{\log e}2\delta^2(1+O(\delta))=1-\frac1{2k}(1+O(\delta)),$$, it should be $$1-\frac{\log e}2\delta^2(1-O(\delta))=1-\frac1{2k}(1-O(\delta)),$$? $\endgroup$
    – A. H.
    Jan 26 at 14:10
  • 1
    $\begingroup$ The two $O(\delta)$ functions on each side are different, of course, hence you can't cancel them. E.g., we have $(1+x)(1+O(x))=(1+2x)(1+O(x))$, but not $x=2x$. $\endgroup$ Jan 26 at 15:57
  • 1
    $\begingroup$ I’m sorry, but I don’t have the time to teach you basic algebraic manipulation with O(...). I subtracted $1$ from both sides, multiplied the equation by $-2/\log e$, divided it by the $1+O(1)$ function from the LHS to get $\delta^2=\frac1{k\log e}(1+O(1))$, and took a square root. This all works because $(1+x)^{-1}=1+O(x)$, $(1+x)(1+y)=1+O(|x|+|y|)$, and $\sqrt{1+x}=1+O(x)$. To solve $\delta=\frac1{\sqrt{k\log e}}(1+O(\delta))$, it is perhaps easiest to do it in two steps: first $\delta$ is a priori bounded, hence weakening the RHS, the equation implies $\delta=O(k^{-1/2})$. Then plug ... $\endgroup$ Jan 30 at 14:21
  • 1
    $\begingroup$ ... this bound to the RHS again to get $\delta=\frac1{\sqrt{k\log e}}(1+O(k^{-1/2}))=\frac1{\sqrt{k\log e}}+O(k^{-1})$. $\endgroup$ Jan 30 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.