Running a BPP algorithm with a half-random, half-adversarial string

Question

Consider the following model: an n-bit string r=r₁...r_n is chosen uniformly at random. Next, each index i∈{1,...,n} is put into a set A with independent probability 1/2. Finally, an adversary is allowed, for each i∈A separately, to flip r_i if it wants to.

My question is this: can the resulting string (call it r') be used by an RP or BPP algorithm as its only source of randomness? Assume that the adversary knows in advance the entire BPP algorithm, the string r, and the set A, and that it has unlimited computation time. Also assume (obviously) that the BPP algorithm knows neither the adversary's flip decisions nor A.

I'm well-aware that there's a long line of work on precisely this sort of question, from Umesh Vazirani's work on semi-random sources (a different but related model), to more recent work on extractors, mergers, and condensers. So my question is simply whether any of that work yields the thing I want! The literature on weak random sources is so large, with so many subtly-different models, that someone who knows that literature can probably save me a lot of time. Thanks in advance!

score 22 · Accepted Answer · edited Mar 15 '12 at 21:32

22

What you need is a "seeded extractor" with the following parameters: seed of length $O(\log n)$, crude randomness $n/2$, and output length $n^{\Omega(1)}$. These are known. While I'm not up to date with the most recent surveys, I believe that section 3 of Ronen's survey is enough.

The only thing you will need to show is that your source has sufficient "min-entropy", i.e. no n-bit string gets a probability of more than $2^{-n/2}$, which I think is clear in your setting.

edited Mar 15 '12 at 21:32

Suresh Venkat

32,071
4
95
271

answered Mar 15 '12 at 20:22

Noam

9,369
47
58

1

Thanks, Noam!! Just looked at Ronen's survey and it looks like it should work. – Scott Aaronson Mar 15 '12 at 23:44

score 5 · Answer 2 · answered Mar 17 '12 at 16:17

Is the adversary allowed to see the entire string r before deciding how to set the bits in A? If the answer is no then this is a bit-fixing source, which is actually deterministically extractable. That is, no truly random seed required. See, for example, Kamp and Zuckerman for constructions of extractors for bit-fixing sources.

If the adversary is allowed to see the rest of the string I would still guess that it's deterministically extractable, but the models are slightly different and I don't know off the top of my head how they relate. Since the set A is random it's actually even friendlier than a bit-fixing source, where the set A may be arbitrary.

Yes, the adversary is allowed to see the whole string. Does Noam's answer not apply in that case? — Scott Aaronson, Mar 19 '12 at 23:44

score 4 · Answer 3 · answered Apr 19 '12 at 18:07

Noam is right, of course. Historically, the first simulation of BPP with a source of any constant entropy rate was given in my paper "Simulating BPP Using a General Weak Random Source." Now there are simpler ways to achieve this and even stronger results.

Deterministic extraction of more than a constant number of bits is impossible in your model. (You can get some weak deterministic extraction of 1 bit by simply outputting the first bit.) Kamp and I showed that it's impossible to extract more than a constant number of bits in a general non-oblivious bit-fixing source with constant entropy rate, but since the set A is random, those results don't apply as stated. However, our proof worked by choosing A at random of a fixed size t, so by choosing t=.6n, say, the result for a uniformly random A will follow.

Running a BPP algorithm with a half-random, half-adversarial string

3 Answers3