Lower bounds on arithmetic circuits via partial derivatives

被引：0
|
作者：
Nisan, N [1 ]
Wigderson, A
机构：
[1] Hebrew Univ Jerusalem, Inst Comp Sci, IL-91905 Jerusalem, Israel
[2] Aarhus Univ, BRICS, DK-8000 Aarhus C, Denmark
来源：
COMPUTATIONAL COMPLEXITY | 1997年 / 6卷 / 03期
关键词：
circuit complexity; arithmetic circuits; lower bounds; iterated matrix product;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper we describe a new technique for obtaining lower bounds on restricted classes of non-monotone arithmetic circuits. The heart of this technique is a complexity measure for multivariate polynomials, based on the linear span of their partial derivatives. We use the technique to obtain new lower bounds for computing symmetric polynomials (that hold over fields of characteristic zero) and iterated matrix products (that hold for all fields).
引用
收藏
页码：217 / 234
页数：18
相关论文
共 50 条
  • [1] Lower Bounds for Arithmetic Circuits via the Hankel Matrix
    Fijalkow, Nathanael
    Lagarde, Guillaume
    Ohlmann, Pierre
    Serre, Olivier
    COMPUTATIONAL COMPLEXITY, 2021, 30 (02)
  • [2] Lower Bounds for Arithmetic Circuits via the Hankel Matrix
    Nathanaël Fijalkow
    Guillaume Lagarde
    Pierre Ohlmann
    Olivier Serre
    computational complexity, 2021, 30
  • [3] Lower Bounds for Arithmetic Circuits via the Hankel Matrix
    Fijalkow, Nathanael
    Lagarde, Guillaume
    Ohlmann, Pierre
    Serre, Olivier
    37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
  • [4] Recent progress on lower bounds for arithmetic circuits
    Saraf, Shubhangi
    2014 IEEE 29TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2014, : 155 - 160
  • [5] Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity
    Chattopadhyay, Arkadev
    Datta, Rajit
    Mukhopadhyay, Partha
    STOC '21: PROCEEDINGS OF THE 53RD ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2021, : 786 - 799
  • [6] Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
    Forbes, Michael A.
    Kumar, Mrinal
    Saptharishi, Ramprasad
    31ST CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2016), 2016, 50
  • [7] Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
    Neeraj Kayal
    Chandan Saha
    computational complexity, 2016, 25 : 419 - 454
  • [8] LOWER BOUNDS FOR DEPTH-THREE ARITHMETIC CIRCUITS WITH SMALL BOTTOM FANIN
    Kayal, Neeraj
    Saha, Chandan
    COMPUTATIONAL COMPLEXITY, 2016, 25 (02) : 419 - 454
  • [9] Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices
    Kumar, Mrinal
    Maheshwari, Gaurav
    Sarma, Jayalal
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2016, 8 (03)
  • [10] Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin
    Kayal, Neeraj
    Saha, Chandan
    30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 158 - 182
12345