首页    期刊浏览 2024年10月06日 星期日
登录注册

文章基本信息

  • 标题:Improved Pseudorandom Generators for Depth 2 Circuits
  • 本地全文:下载
  • 作者:Anindya De ; Omid Etesami ; Luca Trevisan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We prove the existence of a poly(nm) -time computablepseudorandom generator which ``1poly(nm) -fools'' DNFs with n variablesand m terms, and has seed length O(log2nmloglognm).Previously, the best pseudorandom generator for depth-2 circuits had seedlength O(log3nm), and was due to Bazzi (FOCS 2007).

    It follows from our proofthat a 1mO(logmn) -biased distribution 1poly(nm) -fools DNFswith m terms and n variables. For inverse polynomial distinguishing probabilitythis is nearly tight because we show that for every m there is a 1m(log1) -biaseddistribution X and a DNF with m terms such that isnot -fooled by X.

    For the case of {\em read-once} DNFs, we show that seed lengthO(logmnlog1) suffices, which is an improvement for large .

    It also follows from our proof that a 1mO(log1) -biased distribution-fools all read-once DNF with m terms. We show that this result too is nearly tight,by constructing a 1m(log1) -biased distributionthat does not -fool a certain m-term read-once DNF

  • 关键词:DNF; Small bias spaces
国家哲学社会科学文献中心版权所有