首页    期刊浏览 2025年02月21日 星期五
登录注册

文章基本信息

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

    We present an explicit pseudorandom generator for oblivious, read-once, width- 3 branching programs, which can read their input bits in any order. The generator has seed length O ( log 3 n ) The previously best known seed length for this model is n 1 2+ o (1) due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM '13) for \textit{permutation} branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : 0 1 n 0 1 computed by such a branching program, and k [ n ] s [ n ]: s = k f [ s ] n 2 ( O ( log n ) ) k where f [ s ] = E f [ U ] ( − 1 ) s U is the standard Fourier transform over Z n 2 . The base O ( log n ) of the Fourier growth is tight up to a factor of log log n .

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