Some Results on Derandomization

Harry Buhrman, Lance Fortnow, Aduri Pavan

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...

Figure