1
$\begingroup$

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

$\endgroup$
  • 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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.