6
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ What is d in the above ? $\endgroup$ – Suresh Venkat Apr 24 '11 at 2:34
  • $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Apr 24 '11 at 4:42
  • $\begingroup$ 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. $\endgroup$ – Sebastian Ben Daniel Apr 24 '11 at 10:29
  • $\begingroup$ @Noam, maybe that should be an answer ? $\endgroup$ – Suresh Venkat Apr 24 '11 at 16:27
  • $\begingroup$ ok. moved it to be an answer. $\endgroup$ – Noam Apr 24 '11 at 16:38
7
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Sebastian Ben Daniel Apr 24 '11 at 16:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.