# Impagliazzo lemma, unclear detail in its proof

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$ ?

• 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. Jul 22, 2018 at 17:36
• 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$." Jul 22, 2018 at 17:45
• Does it make any difference here whether we have $tS' < S$ or on the other hand weak inequality $tS' \leq S$ ? Jul 22, 2018 at 19:34
• 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}$? Jul 22, 2018 at 19:54
• 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.) Jul 22, 2018 at 19:59