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

文章基本信息

  • 标题:Arithmetic circuits: A chasm at depth three
  • 本地全文:下载
  • 作者:Ankit Gupta ; Pritish Kamath ; Neeraj Kayal
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2013
  • 卷号:2013
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We show that, over Q, if an n-variate polynomial of degree d=nO(1) is computable by an arithmetic circuit of size s (respectively by an algebraic branching program of size s) then it can also be computed by a depth three circuit (i.e. a -circuit) of size exp(dlogdlognlogs) (respectively of size exp(dlognlogs) ). In particular this yields a circuit of size exp(dlogd) computing the dd determinant Detd. It also means that if we can prove a lower bound of exp((dlog32d)) on the size of any -circuit computing the dd permanent Permd then we get superpolynomial lower bounds for the size of any arithmetic circuit computing Permd. We then give some further results pertaining to derandomizing polynomial identity testing and circuit lower bounds. The circuits that we construct have the property that (some of) the intermediate polynomials have degree much higher than d. Indeed such a counterintuitive construction is unavoidable - it is known that in any circuit C computing either Detd or Permd, if every multiplication gate has fanin at most d (or any constant multiple thereof) then C must have size at least exp((d)).

  • 关键词:arithmetic circuits; determinant; lower bounds; sigma-pi-sigma circuits
国家哲学社会科学文献中心版权所有