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

文章基本信息

  • 标题:An exponential lower bound for homogeneous depth-5 circuits over finite fields
  • 本地全文:下载
  • 作者:Mrinal Kumar ; Ramprasad Saptharishi
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    In this paper, we show exponential lower bounds for the class of homogeneous depth- 5 circuits over all small finite fields. More formally, we show that there is an explicit family P d : d N of polynomials in VN P , where P d is of degree d in n = d O (1) variables, such that over all finite fields F q , any homogeneous depth- 5 circuit which computes P d must have size at least exp ( q ( d )) .

    To the best of our knowledge, this is the first super-polynomial lower bound for this class for any field F q = F 2 .

    Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth- 4 circuits [GKKS14, FLMS14, KLSS14, KS14b] and for non-homogeneous depth- 3 circuits over finite fields [GK98, GR00]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from F q n F q as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [KS14b].

  • 关键词:arithmetic circuits ; finite fields ; lower bounds ; Shifted partial derivatives
国家哲学社会科学文献中心版权所有