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 条

[31] Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas [J].

Kayal, Neeraj ;

Limaye, Nutan ;

Saha, Chandan ;

Srinivasan, Srikanth .

STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, :119-127

[32] Lower Bounds for DeMorgan Circuits of Bounded Negation Width [J].

Jukna, Stasys ;

Lingas, Andrzej .

36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,

[33] Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation) [J].

Roughgarden, Tim ;

Vassilvitskii, Sergei ;

Wang, Joshua R. .

JOURNAL OF THE ACM, 2018, 65 (06)

[34] Exponential lower bounds for depth three Boolean circuits [J].

Paturi, R ;

Saks, ME ;

Zane, F .

COMPUTATIONAL COMPLEXITY, 2000, 9 (01) :1-15

[35] Lower bounds for modular counting by circuits with modular gates [J].

Barrington, DAM ;

Straubing, H .

COMPUTATIONAL COMPLEXITY, 1999, 8 (03) :258-272

[36] Lower Bounds and Separations for Constant Depth Multilinear Circuits [J].

Ran Raz ;

Amir Yehudayoff .

computational complexity, 2009, 18 :171-207

[37] LOWER BOUNDS AND SEPARATIONS FOR CONSTANT DEPTH MULTILINEAR CIRCUITS [J].

Raz, Ran ;

Yehudayoff, Amir .

COMPUTATIONAL COMPLEXITY, 2009, 18 (02) :171-207

[38] Lower Bounds: From Circuits to QBF Proof Systems [J].

Beyersdorff, Olaf ;

Bonacina, Ilario ;

Chew, Leroy .

ITCS'16: PROCEEDINGS OF THE 2016 ACM CONFERENCE ON INNOVATIONS IN THEORETICAL COMPUTER SCIENCE, 2016, :249-260

[39] Some lower bounds of cyclic shift on Boolean circuits [J].

Tsukiji, T .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 1996, E79A (04) :520-523

[40] Unifying Known Lower Bounds via Geometric Complexity Theory [J].

Joshua A. Grochow .

computational complexity, 2015, 24 :393-475

← 1 2 3 4 5 →