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

文章基本信息

  • 标题:Pseudorandom Bits for Oblivious Branching Programs
  • 本地全文:下载
  • 作者:Rohit Gurjar ; Ben Lee Volk
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We construct a pseudorandom generator which fools read- k oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are O ( n 1 − 1 2 k − 1 ) (for the read- k case) and O ( n log log n ) (for the linear length case). Previously, the best construction for these models required seed length (1 − (1)) n .

  • 关键词:branching programs ; pseudorandom generator ; Pseudorandomness
国家哲学社会科学文献中心版权所有