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

文章基本信息

  • 标题:Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates
  • 本地全文:下载
  • 作者:Valentine Kabanets ; Zhenjian Lu
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree d on n inputs, our PRG for error has the seed size exp O ( d log n log log ( n ) ) ; this can give a super-polynomial stretch even for a sub-exponentially small error parameter = exp ( − n ) , for any = o (1) . In contrast, the best known PRGs for PTFs of [Meka & Zuckerman, 2013; Kane, 2012] cannot achieve such a small error, although they do have a much shorter seed size for any constant error . For the case of circuits with degree- d PTF gates on n inputs, our PRG can fool circuits with at most n d gates with error exp ( − n d ) and seed length n O ( ) , for any 1"> 1 . While a similar NW PRG construction was observed by Lovett and Srinivasan [Lovett & Srinivasan, 2011] to work for the case of constant-depth (AC 0 ) circuits with few PTF gates, the application of the NW generator to the case of general (unbounded depth) circuits consisting of a sublinear number of PTF gates does not seem to have been explicitly stated before. We do so in this note.

  • 关键词:Nisan-Wigderson generator ; PTF gates
国家哲学社会科学文献中心版权所有