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

  • 4
    $\begingroup$ 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. $\endgroup$ – Clement C. Jul 22 '18 at 17:36
  • 4
    $\begingroup$ 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$." $\endgroup$ – Clement C. Jul 22 '18 at 17:45
  • 2
    $\begingroup$ Does it make any difference here whether we have $tS' < S$ or on the other hand weak inequality $tS' \leq S$ ? $\endgroup$ – user2925716 Jul 22 '18 at 19:34
  • 2
    $\begingroup$ 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}$? $\endgroup$ – user2925716 Jul 22 '18 at 19:54
  • 5
    $\begingroup$ 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.) $\endgroup$ – Clement C. Jul 22 '18 at 19:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.