首页    期刊浏览 2024年11月30日 星期六
登录注册

文章基本信息

  • 标题:Nearly Optimal Pseudorandomness From Hardness
  • 本地全文:下载
  • 作者:Dean Doron ; Dana Moshkovitz ; Justin Oh
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2019
  • 卷号:2019
  • 页码:1-51
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Existing proofs that deduce BPP = P from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length n running in time t n to a deterministic one running in time t 2+ for an arbitrarily small constant 0"> 0 . Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing).Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1 + ) log s , under the assumption that there exists a function f E that requires nondeterministic circuits of size at least 2 (1 − ) n , where = O ( ) . The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

国家哲学社会科学文献中心版权所有