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

文章基本信息

  • 标题:Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
  • 本地全文:下载
  • 作者:Manindra Agrawal ; Michael Forbes ; Sumanta Ghosh
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2017
  • 卷号:2017
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth- 4 circuits, which would yield such results for general circuits (that is, the complexity class VP). We show that if we can design poly( s )-time hitting-sets for a O ( log s ) circuits of size s , where a = (1) is arbitrarily small and the number of variables, or arity n , is O ( log s ) , then we can derandomize blackbox PIT for general circuits in quasipolynomial time. Further, this establishes that either E \#P/poly or that VP = VNP. We call the former model \emph{tiny} diagonal depth- 4 . Note that these are merely polynomials with arity O ( log s ) and degree ( log s ) . In fact, we show that one only needs a poly( s )-time hitting-set against individual-degree a = (1) polynomials that are computable by a size- s arity- ( log s ) circuit (note: fanin may be s ). Alternatively, we claim that, to understand VP one only needs to find hitting-sets, for depth- 3 , that have a small parameterized complexity.

  • 关键词:hitting-set; tiny; arity; depth-3; depth-4; derandomization; identity testing; lower bound; VP
国家哲学社会科学文献中心版权所有