Access Restriction

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

   Open content in new tab
Source: ACM Digital Library