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 条

[41] Certifying Polynomials for AC0[⊕] Circuits, with Applications to Lower Bounds and Circuit Compression [J].

Kopparty, Swastik ;

Srinivasan, Srikanth .

THEORY OF COMPUTING, 2018, 14

[42] New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates [J].

Williams, R. Ryan .

THEORY OF COMPUTING, 2018, 14

[43] Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits [J].

Beck, Chris ;

Impagliazzo, Russell ;

Lovett, Shachar .

2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, :101-110

[44] Lower Bounds for QCDCL via Formula Gauge [J].

Boehm, Benjamin ;

Beyersdorff, Olaf .

JOURNAL OF AUTOMATED REASONING, 2023, 67 (04)

[45] Lower Bounds for QCDCL via Formula Gauge [J].

Boehm, Benjamin ;

Beyersdorff, Olaf .

THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, SAT 2021, 2021, 12831 :47-63

[46] Lower Bounds for QCDCL via Formula Gauge [J].

Benjamin Böhm ;

Olaf Beyersdorff .

Journal of Automated Reasoning, 2023, 67

[47] Scheduling lower bounds via AND subset sum [J].

Abboud, Amir ;

Bringmann, Karl ;

Hermelin, Danny ;

Shabtay, Dvir .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2022, 127 :29-40

[48] ARITHMETIC CIRCUITS: A CHASM AT DEPTH 3 [J].

Gupta, Ankit ;

Kamath, Pritish ;

Kayal, Neeraj ;

Saptharishi, Ramprasad .

SIAM JOURNAL ON COMPUTING, 2016, 45 (03) :1064-1079

[49] Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds [J].

Forbes, Michael A. ;

Shpilka, Amir ;

Volk, Ben Lee .

STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, :653-664

[50] Top-Down Lower Bounds for Depth-Four Circuits [J].

Goos, Mika ;

Riazanov, Artur ;

Sofronova, Anastasia ;

Sokolov, Dmitry .

2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, :1048-1055

← 1 2 3 4 5 →