<p>You can't expect this to be true since you can reduce the error of a constant-error algorithm to <span class="math-container">$1/n$</span> using an additional <span class="math-container">$O(\log n)$</span> bits using expanders (and by the way you don't really need even these extra bits to do that). So if an error of <span class="math-container">$1/n$</span> can go down to <span class="math-container">$\exp(-n)$</span> error using only <span class="math-container">$O(n/\log n)$</span> additional bits, then you could always go from constant error to <span class="math-container">$\exp(-n)$</span> error using <span class="math-container">$O(\log n)+O(n/\log n)=O(n/\log n)$</span>.  </p>

CC BY-SA 3.0
2011-04-24T16:49:01.187Z
Thanks. This means that even if we have a very good algorithm, say with sub exponential error probability, you still need O(n) additional random bits. Hence, for error-reduction it is pretty much useless right? (besides the fact that it can reduce the number of times that the original algorithm is being used)
Sebastian Ben Daniel
CC BY-SA 4.0
2011-04-24T16:41:37.233Z
2019-01-24T02:30:13.317Z
2019-01-24T02:30:13.317Z
Noam
<p>In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a good error probability to begin with, say 1/n, without expanders we need to run it only O(n/log n) times to achieve the same error and use $n^d\times O(n/\log n)$ random bits.
If I'm correct with expanders it doesn't help (beside a little in the first step), meaning we still need $n^d+O(n)$ random bits.
There exist some method, such that a good algorithm does have an affect on it (uses say $n^d+O(n/\log n)$ random bits)? There exist some barrier for achieving such a result?</p>

<p>*The question refers to the randomized algorithm in a black-box manner. </p>

CC BY-SA 3.0
2011-04-24T02:34:36.140Z
What is d in the above ?
Suresh Venkat
CC BY-SA 3.0
2011-04-24T04:42:47.310Z
I see. I don't quite understand the use of 'n^d' to encode the number of bits used by the algorithm, but it sounds like you're asking if the expander trick can capitalize on an already good error probability ?
Suresh Venkat
CC BY-SA 3.0
2011-04-24T10:29:15.917Z
Exactly. $n^d$ means that the algorithm needs that many random bits for an n-length input where d is some constant. In my question the error-probability is non-constant to begin with, however, surprisingly, it seems like it has not affect on the error-reduction with expanders, unlike the case with simple amplification.
Sebastian Ben Daniel
CC BY-SA 3.0
2011-04-24T16:27:16.527Z
@Noam, maybe that should be an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-04-24T16:38:33.943Z
ok.  moved it to be an answer.
Noam
<cc.complexity-theory><randomness><derandomization><expanders>
Error reduction with expanders and derandomization
Sebastian Ben Daniel
# Error reduction with expanders and derandomization

(Asked by: username_0 on 2011-04-24)

In "standard" error reduction with an expander, if a randomize algorithm uses $n^d$ random bits, we need $n^d+O(n)$ random bits to achieve $2^{-O(n)}$ error probability.
Now, if the algorithm has a good error probability to begin with, say 1/n, without expanders we need to run it only O(n/log n) times to achieve the same error and use $n^d\times O(n/\log n)$ random bits.
If I'm correct with expanders it doesn't help (beside a little in the first step), meaning we still need $n^d+O(n)$ random bits.
There exist some method, such that a good algorithm does have an affect on it (uses say $n^d+O(n/\log n)$ random bits)? There exist some barrier for achieving such a result?

\*The question refers to the randomized algorithm in a black-box manner.

**Tags:** cc.complexity-theory, randomness, derandomization, expanders

> **Comments:**
> **username_1**: What is d in the above ?  
> **username_1**: I see. I don't quite understand the use of 'n^d' to encode the number of bits used by the algorithm, but it sounds like you're asking if the expander trick can capitalize on an already good error probability ?  
> **username_0**: Exactly. $n^d$ means that the algorithm needs that many random bits for an n-length input where d is some constant. In my question the error-probability is non-constant to begin with, however, surprisingly, it seems like it has not affect on the error-reduction with expanders, unlike the case with simple amplification.  
> **username_1**: @username_2, maybe that should be an answer ?  
> **username_2**: ok.  moved it to be an answer.  

---

## 1 answers

### Answer by username_2 on 2011-04-24. Score: 7 | Accepted answer

You can't expect this to be true since you can reduce the error of a constant-error algorithm to $1/n$ using an additional $O(\log n)$ bits using expanders (and by the way you don't really need even these extra bits to do that). So if an error of $1/n$ can go down to $\exp(-n)$ error using only $O(n/\log n)$ additional bits, then you could always go from constant error to $\exp(-n)$ error using $O(\log n)+O(n/\log n)=O(n/\log n)$.

> **Comments:**
> **username_0**: Thanks. This means that even if we have a very good algorithm, say with sub exponential error probability, you still need O(n) additional random bits. Hence, for error-reduction it is pretty much useless right? (besides the fact that it can reduce the number of times that the original algorithm is being used)  

---

