Some Results on Derandomization
Lists
Only you see this
Abstract
We show several results about derandomization including 1. If NP is easy on average then efficient pseudorandom generators exist and P = BPP. 2. If NP is easy on average then given an NP machine M we can easily on average find accepting computations of M(x) when it accepts. 3. For any A in EXP, if NEXPA is in PA/poly then NEXPA = EXPA. 4. If A is ⌆p k -complete and NEXPA is in PA/poly then NEXPA = EXP = MAA.
BibTeX
@inproceedings{buhrman2003some,
author = {Harry Buhrman and Lance Fortnow and Aduri Pavan},
title = {{Some Results on Derandomization}},
booktitle = {STACS},
year = {2003},
doi = {10.1007/3-540-36494-3\_20},
}Loading related content...