首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:Pseudorandomness for Permutation Branching Programs Without the Group Theory
  • 本地全文:下载
  • 作者:Thomas Steinke
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We exhibit an explicit pseudorandom generator that stretches an Ow4logw+log(1)logn -bit random seed to n pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width w with probability more than . This improves on the seed length O(w!)11+log(1)logn of Koucky, Nimbhorkar, and Pudlak and Ow8+log(1)logn of De. More importantly, the analysis of our generator uses only combinatorial and linear-algebraic arguments, whereas the previous proofs refer to groups or representation theory.

  • 关键词:INW generator; permutation branching programs; pseudorandom generators for small-space computation
国家哲学社会科学文献中心版权所有