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 条
[21]   OPTIMAL LOWER BOUNDS ON THE DEPTH OF POLYNOMIAL-SIZE THRESHOLD CIRCUITS FOR SOME ARITHMETIC FUNCTIONS [J].
WEGENER, I .
INFORMATION PROCESSING LETTERS, 1993, 46 (02) :85-87
[22]   A LOWER BOUND FOR THE SIZE OF SYNTACTICALLY MULTILINEAR ARITHMETIC CIRCUITS [J].
Raz, Ran ;
Shpilka, Amir ;
Yehudayoff, Amir .
SIAM JOURNAL ON COMPUTING, 2008, 38 (04) :1624-1647
[23]   Lower bounds for (MODp,MODm) circuits [J].
Grolmusz, V ;
Tardos, A .
SIAM JOURNAL ON COMPUTING, 2000, 29 (04) :1209-1222
[24]   Unifying Known Lower Bounds via Geometric Complexity Theory [J].
Grochow, Joshua A. .
COMPUTATIONAL COMPLEXITY, 2015, 24 (02) :393-475
[25]   Recent lower bounds for geometric-arithmetic index [J].
Portilla, Ana ;
Rodriguez, Jose M. ;
Sigarreta, Jose M. .
DISCRETE MATHEMATICS LETTERS, 2019, 1 :59-82
[26]   Lower Bounds for Tropical Circuits and Dynamic Programs [J].
Jukna, Stasys .
THEORY OF COMPUTING SYSTEMS, 2015, 57 (01) :160-194
[27]   Lower bounds for Boolean circuits of bounded negation [J].
Jukna, Stasys ;
Lingas, Andrzej .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 129 :90-105
[28]   Lower Bounds for Tropical Circuits and Dynamic Programs [J].
Stasys Jukna .
Theory of Computing Systems, 2015, 57 :160-194
[29]   Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits [J].
Limaye, Nutan ;
Srinivasan, Srikanth ;
Tavenas, Sebastien .
2021 IEEE 62ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2021), 2022, :804-814
[30]   Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits [J].
Forbes, Michael A. ;
Shpilka, Amir ;
Volk, Ben Lee .
THEORY OF COMPUTING, 2018, 14
12345