gotchaMinor
Why does a polytime hitting set generator derandomize RP?
Viewed 0 times
hittingwhypolytimederandomizegeneratordoesset
Problem
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$?
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$?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#138881, answer score: 4
Revisions (0)
No revisions yet.