<p>In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size of $S'=\frac{\epsilon^2 S}{100n}$ from the top line on that page $378$ ?</p>

CC BY-SA 4.0
2018-07-22T17:36:57.737Z
Do not add a link to a not-very-legal PDF version of a book. If you need, refer to the (freely and legally available) [draft of the book.](http://theory.cs.princeton.edu/complexity/)
Clement C.
CC BY-SA 4.0
2018-07-22T17:45:34.603Z
Regarding your question: the goal is to have $tS' \leq S$, since $tS'$ is the bound they obtain on the circuit $C$ they construct. This is stated in the middle of the proof: "Note that the size of $C$ is $tS' < S$."
Clement C.
CC BY-SA 4.0
2018-07-22T19:34:03.610Z
Does it make any difference here whether we have $tS' < S$ or on the other hand weak inequality $tS' \leq S$ ?
user2925716
CC BY-SA 4.0
2018-07-22T19:37:31.390Z
Not really. ${}{}{}$
Clement C.
CC BY-SA 4.0
2018-07-22T19:54:59.193Z
The reason is somewhat circular: we chose the weired constant 50 to get another weired constant $100$. So why did we choose $100$ in $S'=\frac{\epsilon^2 S}{100n}$?
user2925716
CC BY-SA 4.0
2018-07-22T19:59:33.527Z
I would strongly suggest you not only read the proof line by line, but attempt to derive the details on the side. Specifically, the part stating "By a Chernoff bound [...]." This is where you need an extra "weird constant": you want to achieve agreement of $C$ and $f$ on every single fixed "good" $x$, with probability at least $1-2^{-n}$. Derive what bound you need on $t$ for that: the $\epsilon^2$ comes from the definition of "good," the $n$ comes from the $2^{-n}$, and the "weird constant" comes from those in the Chernoff bound. (You may not get $100$, but you will get *some* constant.)
Clement C.
CC BY-SA 4.0
2018-07-24T15:36:10.237Z
I do not follow how do I get $\epsilon^2$ from the definition of "good" and also how do I apply the Chernoff's bound and what constant do I get? Could you be please more specific about these two constants?
user2925716
CC BY-SA 4.0
2018-07-24T16:18:59.797Z
I mean the thing that the r.h.s. of the Chernoff's bound is $2\cdot e^{-\min\{c^2/4,c/2\}\mu}$ so the term after $2\cdot$ is $\leq 1$ so how do I get $100$?
user2925716
CC BY-SA 4.0
2018-07-24T21:13:55.663Z
What is $c$ in what you wrote?! Fix any good $x$. For any given $t\geq 1$, for all $1\leq i\leq t$, by definition the probability that the random $C_i\in\mathcal{C}$ agrees with $f(x)$ (call this event $X_i$) is $\mathbb{E}[X_i] \geq 1/2+\varepsilon$, so apply a Chernoff bound to $X \stackrel{\rm def}{=} \sum_{i=1}^t X_i$ which has $\mathbb{E}[X] \geq t/2+t\varepsilon$: $$\mathbb{P}\{X \leq t/2\} \leq \mathbb{P}\{X \leq \mathbb{E}[X] - t\varepsilon\} \leq e^{-C t\varepsilon^2}$$ for some absolute constant $C>0$ from the statement of the Chernoff bound. Continue
Clement C.
CC BY-SA 4.0
2018-07-25T14:17:20.217Z
Please which version of the Chernoff's bound do you use?
user2925716
CC BY-SA 4.0
2018-07-25T14:23:34.210Z
I use this:Let $X_1,X_2, . . . ,X_n$ be mutually independent random
variables over {0, 1} (i.e., $X_i$ can be either 0 or 1) and let μ =$\sum E[X_i]$
then for every $c > 0$ $Pr[|\sum_{i=1}^n X_i-\mu|\geq c\mu ]\leq2\cdot e^{-\min\{ c^2/4,c/2\}\mu}$
user2925716
CC BY-SA 4.0
2018-07-25T17:01:51.667Z
Then adapt the above  Your $c$ will be some constant times $\varepsilon$, and $\mu$ equals...
Clement C.
CC BY-SA 4.0
2018-07-25T17:05:37.673Z
But overall, you attach WAY too much importance to the constants 50 (and 100). Applying Chernoff, you will see you need to have *some* constant in the setting of $t$ for the argument to go through. 50 works and is "simple", that's why they wrote 50. You may find another, smaller constant - that's not important (constant factors are constant factors...). What matters is that, for the constant you choose, the proof goes through.
Clement C.
CC BY-SA 4.0
2018-07-25T19:22:18.937Z
I wouldn't ask if the constant were something reasonable, say 2 or 4. Would that work? I wonder where is the treshold for what works and what doesn't.And of course, **why**.
user2925716
CC BY-SA 4.0
2018-07-25T19:23:56.360Z
The best way to see it is to try to prove it. You'll see if it works. You have the tools to do that: you have the Chernoff bound, and the outline of what to do.
Clement C.
CC BY-SA 4.0
2018-07-25T19:45:37.503Z
I thought about it for a while, and I can only take $t=1$ but I do not know at all what to take for $C>0$ and $\epsilon$.Could you please give me a hint?
user2925716
CC BY-SA 4.0
2018-07-26T16:44:58.597Z
@ClementC.Do you please have some more hint for me I asked you about?
user2925716
CC BY-SA 4.0
2018-07-26T16:54:02.000Z
This is not the right platform for this (your question does not really fall under the "research-level" umbrella). You appear to be quite confused about what to prove, based on your comment "I can only take $t=1$." *No*: $t$ is the parameter you need to choose, as a function of $n,\varepsilon$, so that $$e^{-c t\varepsilon^2} < 2^{-n}$$ (from my comment above).  Based on e.g. [this, eq (1)](http://www.cs.columbia.edu/~rocco/Teaching/S14/Readings/chernoffbounds.pdf), you can use $c=2$, which would result in the need for $t>\frac{n}{\varepsilon^2}\cdot \frac{\ln 2}{2}$.
Clement C.
CC BY-SA 4.0
2018-07-26T18:44:28.943Z
@ClementC. From what you write it seems to me that $1$ instead of $50$ works as well since $\frac{\ln 2}{2}<1$
user2925716
CC BY-SA 4.0
2018-07-26T18:47:48.780Z
1). I didn't use the same Chernoff bound (I actually used Hoeffding). 2). I may have made mistakes when deriving the result, since I'm basing the last comment on a previous comment I had written; and more importantly, 3). **Constants do not matter**: "50" stands for "some constant that works." Had they written 1000 instead, it'd be fine. The key is, if you want to optimize the constant, do it, but conceptually the theorem is exactly the same. You are way too stuck on this detail, while it's utterly irrelevant to the theorem.
Clement C.
CC BY-SA 4.0
2018-07-26T18:54:01.390Z
OK, but my original question was **why** 50 ? After a run of comments and questions you were not able to produce a sound answer. So **at least** my original question was not that easy as you claimed : "(your question does not really fall under the "research-level" umbrella)."
user2925716
CC BY-SA 4.0
2018-07-26T18:55:13.520Z
It is clear. Why? Because 50 works, and the exact constant does not matter, so they wrote 50 instead of *"$c$, for some suitable constant $c>0$ to be determined in the course of the argument."* You are looking at a tree, arguing about whether it's a red pine or a jack pine, forgetting that the point was to prove existence of a forest.
Clement C.
CC BY-SA 4.0
2018-07-28T13:05:31.360Z
@Dilworth I appreciate very much your comment. I've nearly begun to believe that the problem is on my side. But in any case I read the book seriously and in every detail since I enjoy those aspects you've mentioned. Also I came across an errata to that book [here](https://people.cs.umass.edu/~immerman/cs601/AroraBarakErrata.html) but it doesn't seem to cover all the principal inaccuracies . In most cases the truth can be found after several inspections of the text, but it is not so for my $50$ number problem, at least to to best of my knowledge.
user2925716
<ds.algorithms><circuit-complexity><circuits><two-player-games>
Impagliazzo lemma, unclear detail in its proof
user2925716
# Impagliazzo lemma, unclear detail in its proof

(Asked by: username_0 on 2018-07-22)

In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size of $S'=\frac{\epsilon^2 S}{100n}$ from the top line on that page $378$ ?

**Tags:** ds.algorithms, circuit-complexity, circuits, two-player-games

> **Comments:**
> **username_1**: Do not add a link to a not-very-legal PDF version of a book. If you need, refer to the (freely and legally available) [draft of the book.](http://theory.cs.princeton.edu/complexity/)  
> **username_1**: Regarding your question: the goal is to have $tS' \leq S$, since $tS'$ is the bound they obtain on the circuit $C$ they construct. This is stated in the middle of the proof: "Note that the size of $C$ is $tS' < S$."  
> **username_0**: Does it make any difference here whether we have $tS' < S$ or on the other hand weak inequality $tS' \leq S$ ?  
> **username_1**: Not really. ${}{}{}$  
> **username_0**: The reason is somewhat circular: we chose the weired constant 50 to get another weired constant $100$. So why did we choose $100$ in $S'=\frac{\epsilon^2 S}{100n}$?  
> **username_1**: I would strongly suggest you not only read the proof line by line, but attempt to derive the details on the side. Specifically, the part stating "By a Chernoff bound [...]." This is where you need an extra "weird constant": you want to achieve agreement of $C$ and $f$ on every single fixed "good" $x$, with probability at least $1-2^{-n}$. Derive what bound you need on $t$ for that: the $\epsilon^2$ comes from the definition of "good," the $n$ comes from the $2^{-n}$, and the "weird constant" comes from those in the Chernoff bound. (You may not get $100$, but you will get *some* constant.)  
> **username_0**: I do not follow how do I get $\epsilon^2$ from the definition of "good" and also how do I apply the Chernoff's bound and what constant do I get? Could you be please more specific about these two constants?  
> **username_0**: I mean the thing that the r.h.s. of the Chernoff's bound is $2\cdot e^{-\min\{c^2/4,c/2\}\mu}$ so the term after $2\cdot$ is $\leq 1$ so how do I get $100$?  
> **username_1**: What is $c$ in what you wrote?! Fix any good $x$. For any given $t\geq 1$, for all $1\leq i\leq t$, by definition the probability that the random $C_i\in\mathcal{C}$ agrees with $f(x)$ (call this event $X_i$) is $\mathbb{E}[X_i] \geq 1/2+\varepsilon$, so apply a Chernoff bound to $X \stackrel{\rm def}{=} \sum_{i=1}^t X_i$ which has $\mathbb{E}[X] \geq t/2+t\varepsilon$: $$\mathbb{P}\{X \leq t/2\} \leq \mathbb{P}\{X \leq \mathbb{E}[X] - t\varepsilon\} \leq e^{-C t\varepsilon^2}$$ for some absolute constant $C>0$ from the statement of the Chernoff bound. Continue  
> **username_0**: Please which version of the Chernoff's bound do you use?  
> **username_0**: I use this:Let $X_1,X_2, . . . ,X_n$ be mutually independent random variables over {0, 1} (i.e., $X_i$ can be either 0 or 1) and let μ =$\sum E[X_i]$ then for every $c > 0$ $Pr[|\sum_{i=1}^n X_i-\mu|\geq c\mu ]\leq2\cdot e^{-\min\{ c^2/4,c/2\}\mu}$  
> **username_1**: Then adapt the above  Your $c$ will be some constant times $\varepsilon$, and $\mu$ equals...  
> **username_1**: But overall, you attach WAY too much importance to the constants 50 (and 100). Applying Chernoff, you will see you need to have *some* constant in the setting of $t$ for the argument to go through. 50 works and is "simple", that's why they wrote 50. You may find another, smaller constant - that's not important (constant factors are constant factors...). What matters is that, for the constant you choose, the proof goes through.  
> **username_0**: I wouldn't ask if the constant were something reasonable, say 2 or 4. Would that work? I wonder where is the treshold for what works and what doesn't.And of course, **why**.  
> **username_1**: The best way to see it is to try to prove it. You'll see if it works. You have the tools to do that: you have the Chernoff bound, and the outline of what to do.  
> **username_0**: I thought about it for a while, and I can only take $t=1$ but I do not know at all what to take for $C>0$ and $\epsilon$.Could you please give me a hint?  
> **username_0**: @ClementC.Do you please have some more hint for me I asked you about?  
> **username_1**: This is not the right platform for this (your question does not really fall under the "research-level" umbrella). You appear to be quite confused about what to prove, based on your comment "I can only take $t=1$." *No*: $t$ is the parameter you need to choose, as a function of $n,\varepsilon$, so that $$e^{-c t\varepsilon^2} < 2^{-n}$$ (from my comment above).  Based on e.g. [this, eq (1)](http://www.cs.columbia.edu/~rocco/Teaching/S14/Readings/chernoffbounds.pdf), you can use $c=2$, which would result in the need for $t>\frac{n}{\varepsilon^2}\cdot \frac{\ln 2}{2}$.  
> **username_0**: @ClementC. From what you write it seems to me that $1$ instead of $50$ works as well since $\frac{\ln 2}{2}<1$  
> **username_1**: 1). I didn't use the same Chernoff bound (I actually used Hoeffding). 2). I may have made mistakes when deriving the result, since I'm basing the last comment on a previous comment I had written; and more importantly, 3). **Constants do not matter**: "50" stands for "some constant that works." Had they written 1000 instead, it'd be fine. The key is, if you want to optimize the constant, do it, but conceptually the theorem is exactly the same. You are way too stuck on this detail, while it's utterly irrelevant to the theorem.  
> **username_0**: OK, but my original question was **why** 50 ? After a run of comments and questions you were not able to produce a sound answer. So **at least** my original question was not that easy as you claimed : "(your question does not really fall under the "research-level" umbrella)."  
> **username_1**: It is clear. Why? Because 50 works, and the exact constant does not matter, so they wrote 50 instead of *"$c$, for some suitable constant $c>0$ to be determined in the course of the argument."* You are looking at a tree, arguing about whether it's a red pine or a jack pine, forgetting that the point was to prove existence of a forest.  
> **username_0**: @Dilworth I appreciate very much your comment. I've nearly begun to believe that the problem is on my side. But in any case I read the book seriously and in every detail since I enjoy those aspects you've mentioned. Also I came across an errata to that book [here](https://people.cs.umass.edu/~immerman/cs601/AroraBarakErrata.html) but it doesn't seem to cover all the principal inaccuracies . In most cases the truth can be found after several inspections of the text, but it is not so for my $50$ number problem, at least to to best of my knowledge.  

---

## 0 answers

