A new general derandomization methodA new general derandomization method

Access Restriction
Subscribed

 Author Andreev, Alexander E. ♦ Clementi, Andrea E F ♦ Rolim, Jos D P Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1998 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword BPP ♦ Boolean circuits ♦ Derandomization Abstract We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms.Our method is based on a deterministic algorithm that, given a Boolean circuit $\textit{C}$ and given access to a hitting set generator, constructs a discrepancy set for $\textit{C}.$ The main novelty is that the discrepancy set depends on $\textit{C},$ so the new derandomization method is not uniform (i.e., not $\textit{oblivious}).The$ algorithm works in time exponential in $\textit{k(p(n))}$ where $\textit{k}(*)$ is the $\textit{price}$ of the hitting set generator and $\textit{p}(*)$ is a polynomial function in the size of $\textit{C}.$ We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1998-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 45 Issue Number 1 Page Count 35 Starting Page 179 Ending Page 213

Open content in new tab

Source: ACM Digital Library