4
$\begingroup$

I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not only imply $\mathsf{RP = P}$ but $\mathsf{BPP = P}$ as well, but I can't even conceptualize why the former holds.

The paper states that

Having such a generator that runs in polynomial time enables a trivial deterministic simulation of an RP algorithm by using each of the generator’s outputs as the random pad of the given algorithm.

Every paper or lecture notes I've found on the topic of HSGs and $\mathsf{BPP}$ derandomization also mentions that $\mathsf{RP}$ derandomization is trivial using an HSG, simply by trying all elements of the hitting set as random pads.

I am confused as to why this is the case. At least one element of a hitting set must be accepted by circuits that accept over half of their inputs. However, RP circuits don't necessarily accept over half their inputs; rather, if $x \in L$, only then will the circuit accept over half the time. I assume that fact is related to why a hitting set must contain a valid $\mathsf{RP}$ random pad, but I do not understand exactly how.

So, my question is: how do the circuits in the definition of an HSG relate exactly to $\mathsf{RP}$ circuits? i.e. how do the elements of the hitting set - which are to be the random pads across all inputs - relate to the randomness of RP algorithms when such algorithms accept over half the time only when $x \in L$?

Improve this question
$\endgroup$
4
$\begingroup$

The point is that instead of checking what happens for all possible random strings, you can reduce the search to the output of the generator.

Let $M(x,r)$ be some RP machine for a language $L$, i.e. if $x\in L$ at least two thirds of the $r$'s lead to acceptance, and if $x\notin L$ there is no $r$ for which $M(x,r)$ accepts. Now, Given input $x$, construct a circuit $C_x(r)=M(x,r)$ and execute the generator $G\left(p(|x|),|C_x|\right)$, where $p(n)$ is the number of random bits used by $M$ on a length $n$ input. This yields a set $R$ of polynomially many strings, now simply check whether or not $C_x(r)$ accepts at least one element from $R$. This doesn't straightforwardly generalizes to BPP since in that case it might be the case that $x\notin L$ but $C_x(r)$ accepts some strings from $R$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks for the answer. I understand that we make the search for pads efficient because the output of the generator is polysize, but not why we can "simply check whether or not 𝐶𝑥(𝑟) accepts at least one element from 𝑅." Why is at least one element of $R$ guaranteed to a be good RP pad? $\endgroup$ – Josh Katofsky Apr 13 at 14:39
  • $\begingroup$ To elaborate, I don't see why 𝐶𝑥(𝑟) would accept over half of its inputs. $\endgroup$ – Josh Katofsky Apr 13 at 14:52
  • $\begingroup$ It follows from $M$ being an "RP machine" for $L$, for inputs in the language at least two thirds of the random strings lead to acceptance, for inputs outside the language no random string leads to acceptance. $\endgroup$ – Ariel Apr 13 at 15:06
  • $\begingroup$ I think there's something I'm just not getting; since we also have to deal with the case $x \not\in L$, why does this work? Wouldn't $C_x$ be the "circuit that accepts over half its inputs" only in the case that $x \in L$? $\endgroup$ – Josh Katofsky Apr 13 at 15:19
  • 1
    $\begingroup$ Ah! Understood. I think I just needed it said to me a few times before it made sense. Thank you! $\endgroup$ – Josh Katofsky Apr 13 at 15:33

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.