2
$\begingroup$

Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case input to a series of random instances. The proof is rather straight forward, but I am having trouble replicating the final error bound.

In particular, randomized algorithm $A'$ is said to run algorithm $A$ $O(\frac{1}{\delta \log \frac{1}{\epsilon}})$ times. $A$ succeeds with probability $\delta$, so one possible bound of the error probability of $A'$ should be

$$ \mathbb{P}[A' \text{ fails }] = (1 - \delta)^{\frac{1}{\delta \log\frac{1}{\epsilon}}} \leq (e^{-\delta})^{\frac{1}{\delta \log\frac{1}{\epsilon}}} = e^{\frac{1}{\log \epsilon}} \neq \epsilon $$

Arora and Barak are able to achieve the bound $\mathbb{P}[A' \text{ fails }] \leq \epsilon$, but it seems my attempts have resulted in loose bounds. I'd love some direction as to how I could potentially reach the tighter bound that the textbook achieves.

Alternatively, because the book is a draft, it is possible this is a typo. With $O(\frac{\log \frac{1}{\epsilon}}{\delta})$ runs of $A$, my simple technique above is able to reach the $\epsilon$ bound.

(https://theory.cs.princeton.edu/complexity/book.pdf)

$\endgroup$
2
  • 2
    $\begingroup$ Yes, that's a typo. $\endgroup$
    – Clement C.
    Nov 8 at 23:37
  • 2
    $\begingroup$ Agreed, for example for $\delta \approx 1$ it says to run it $o(1)$ times as $\epsilon\to 0$. That makes no sense. $\endgroup$
    – Neal Young
    Nov 9 at 3:08

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy