<p>Section 10.1.2 of Sanjeev Arora and Boaz Barak's <em>Computational Complexity: A Modern Approach</em> 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.</p>
<p>In particular, randomized algorithm <span class="math-container">$A'$</span> is said to run algorithm <span class="math-container">$A$</span> <span class="math-container">$O(\frac{1}{\delta \log \frac{1}{\epsilon}})$</span> times. <span class="math-container">$A$</span> succeeds with probability <span class="math-container">$\delta$</span>, so one possible bound of the error probability of <span class="math-container">$A'$</span> should be</p>
<p><span class="math-container">$$
\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
$$</span></p>
<p>Arora and Barak are able to achieve the bound <span class="math-container">$\mathbb{P}[A' \text{ fails }] \leq \epsilon$</span>, 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.</p>
<p>Alternatively, because the book is a draft, it is possible this is a typo. With <span class="math-container">$O(\frac{\log \frac{1}{\epsilon}}{\delta})$</span> runs of <span class="math-container">$A$</span>, my simple technique above is able to reach the <span class="math-container">$\epsilon$</span> bound.</p>
<p>(<a href="https://theory.cs.princeton.edu/complexity/book.pdf" rel="nofollow noreferrer">https://theory.cs.princeton.edu/complexity/book.pdf</a>)</p>

CC BY-SA 4.0
2022-11-08T23:37:15.283Z
Yes, that's a typo.
Clement C.
CC BY-SA 4.0
2022-11-09T03:08:09.053Z
Agreed, for example for $\delta \approx 1$ it says to run it $o(1)$ times as $\epsilon\to 0$.  That makes no sense.
Neal Young
<cc.complexity-theory><randomized-algorithms>
Random Self-Reducibility of the Discrete Logarithm
Krish Singal
# Random Self-Reducibility of the Discrete Logarithm

(Asked by: username_0 on 2022-11-08)

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>)

**Tags:** cc.complexity-theory, randomized-algorithms
> **Comments:**
> **username_1**: Yes, that's a typo.  
> **username_2**: Agreed, for example for $\delta \approx 1$ it says to run it $o(1)$ times as $\epsilon\to 0$.  That makes no sense.  

---

## 0 answers

