<p><span class="math-container">$\let\ep\varepsilon$</span>Note that the stated estimate <span class="math-container">$\tilde O\bigl(2^{H(\ep)n}\bigr)$</span> on the volume of the Hamming ball only holds for <span class="math-container">$\ep\le1/2$</span> (for <span class="math-container">$\ep\ge1/2$</span>, it stays <span class="math-container">$\Theta(2^n)$</span>). As the paper says, in order to optimize the sum, a good choice is <span class="math-container">$\ep\le1/2$</span> such that <span class="math-container">$H(\ep)=1-\ep/k$</span>.</p>
<p>For <span class="math-container">$k$</span> large, this is close to <span class="math-container">$1$</span>, and <span class="math-container">$H(\ep)$</span> is close to <span class="math-container">$1$</span> for <span class="math-container">$\ep$</span> close to <span class="math-container">$1/2$</span>. Thus, write <span class="math-container">$\ep=\frac12(1-\delta)$</span>, <span class="math-container">$\delta\ge0$</span>, and compute the asymptotics of <span class="math-container">$H(\ep)$</span> for small <span class="math-container">$\delta$</span>:
<span class="math-container">$$\begin{align*}
H(\ep)&amp;=\ep\bigl(1-\log(1-\delta)\bigr)+(1-\ep)\bigl(1-\log(1+\delta)\bigr)\\
&amp;=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\\
&amp;=1-(1-2\ep)\delta\log e+\tfrac12\delta^2\log e+O(\delta^3)\\
&amp;=1-\frac{\log e}2\delta^2+O(\delta^3).
\end{align*}$$</span>
The equation <span class="math-container">$H(\ep)=1-\ep/k$</span> becomes
<span class="math-container">$$1-\frac{\log e}2\delta^2(1+O(\delta))=1-\frac1{2k}(1+O(\delta)),$$</span>
thus <span class="math-container">$\delta=\frac1{\sqrt{k\log e}}(1+O(\delta))$</span>, which solves to
<span class="math-container">$$\delta=\frac1{\sqrt{k\log e}}+O(k^{-1}).$$</span>
Plugging this back, <span class="math-container">$\ep$</span> satisfies
<span class="math-container">$$H(\ep)=1-\frac\ep k=1-\frac1{2k}+\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$</span>
So, we get
<span class="math-container">$$c_k=\frac1{2k}-\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$</span></p>

CC BY-SA 4.0
2024-01-26T12:46:10.647Z
Why you considered remaining expansion of $\log(1-\delta)$ after $\delta^2$ is $O(\delta^3)?$
the_tomato
CC BY-SA 4.0
2024-01-26T12:56:13.903Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2024-01-26T14:10:10.643Z
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)),$$?
the_tomato
CC BY-SA 4.0
2024-01-26T14:51:21.197Z
That’s exactly the same thing. The definition of $O(\delta)$ does not in any way constrain the sign of the function, only its absolute value.
Emil Jeřábek
CC BY-SA 4.0
2024-01-26T14:53:58.200Z
$$\delta=\frac1{\sqrt{k\log e}}$$ only because $1+O(\delta)$ should be cancelled from both sides?
the_tomato
CC BY-SA 4.0
2024-01-26T14:56:38.190Z
Please tell me you are not being serious.
Emil Jeřábek
CC BY-SA 4.0
2024-01-26T15:34:11.730Z
I understand everything but why $$\delta=\frac1{\sqrt{k\log e}}$$ multiplied by $1+O(\delta)$ not understand, if I ask wrong question please forgive me.
the_tomato
CC BY-SA 4.0
2024-01-26T15:57:33.840Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2024-01-30T14:21:31.013Z
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 ...
Emil Jeřábek
CC BY-SA 4.0
2024-01-30T14:23:24.347Z
... 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})$.
Emil Jeřábek
CC BY-SA 4.0
2024-01-30T17:40:14.457Z
In the previous comments, $O(1)$ should read $O(\delta)$. Sorry for the typos.
Emil Jeřábek
CC BY-SA 4.0
2024-01-26T09:36:51.267Z
2024-01-26T09:57:29.137Z
2024-01-26T09:57:29.137Z
Emil Jeřábek
<p>I am trying to understand  PPZ (Paturi, Pudlák, Zane) derandomization algorithm for <strong>k-SAT</strong>, it seems to be very difficult for me. The last line in the below of the image, I don't understand the time complexity.</p>
<p>My question is how to get at most
<span class="math-container">$\widetilde{O}(2^{n(1−c_k)})$</span> time for <span class="math-container">$c_k = \frac{1}{2k} − o(\frac{1}{2})$</span>, where the asymptotics in <span class="math-container">$o(. . .)$</span> is when <span class="math-container">$k\to\infty$</span>?</p>
<p><a href="https://i.sstatic.net/mC5vG.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mC5vG.jpg" alt="enter image description here" /></a></p>
<p>Details of the note is <a href="https://drive.google.com/file/d/1PrZCZOO9yL-Ls1k0wsgJXcHKVin9f0X_/view?usp=drivesdk" rel="nofollow noreferrer">here.</a> Above image is 1.3 section of this PDF.</p>

CC BY-SA 4.0
2024-01-25T04:55:17.427Z
What is [$\widetilde{O}(n)$](https://stackoverflow.com/questions/1801135/what-is-the-meaning-of-o-polylogn-in-particular-how-is-polylogn-defined)?
the_tomato
<time-complexity><sat>
Time complexity of PPZ algorithm
the_tomato
# Time complexity of PPZ algorithm

(Asked by: username_0 on 2024-01-23)

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](https://i.sstatic.net/mC5vG.jpg)](https://i.sstatic.net/mC5vG.jpg)

Details of the note is [here.](https://drive.google.com/file/d/1PrZCZOO9yL-Ls1k0wsgJXcHKVin9f0X_/view?usp=drivesdk) Above image is 1.3 section of this PDF.

**Tags:** time-complexity, sat

> **Comments:**
> **username_0**: What is [$\widetilde{O}(n)$](https://stackoverflow.com/questions/1801135/what-is-the-meaning-of-o-polylogn-in-particular-how-is-polylogn-defined)?  

---

## 1 answers

### Answer by username_1 on 2024-01-26. Score: 5 | Accepted answer

$\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}).$$

> **Comments:**
> **username_0**: Why you considered remaining expansion of $\log(1-\delta)$ after $\delta^2$ is $O(\delta^3)?$  
> **username_1**: 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$.  
> **username_0**: 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)),$$?  
> **username_1**: That’s exactly the same thing. The definition of $O(\delta)$ does not in any way constrain the sign of the function, only its absolute value.  
> **username_0**: $$\delta=\frac1{\sqrt{k\log e}}$$ only because $1+O(\delta)$ should be cancelled from both sides?  
> **username_1**: Please tell me you are not being serious.  
> **username_0**: I understand everything but why $$\delta=\frac1{\sqrt{k\log e}}$$ multiplied by $1+O(\delta)$ not understand, if I ask wrong question please forgive me.  
> **username_1**: 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$.  
> **username_1**: 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 ...  
> **username_1**: ... 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})$.  
> **username_1**: In the previous comments, $O(1)$ should read $O(\delta)$. Sorry for the typos.  

---

