Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.

DOI10.1007/S002009900021MaRDI QIDQ1573765zbMATH OpenOpenAlexFDO

Authors Dima Grigoriev, Alexander Razborov

Publication date 8 August 2000

Published in Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002009900021

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 1775446
• Depth-3 arithmetic circuits over fields of characteristic zero
• scientific article; zbMATH DE number 1559525
• Exponential size lower bounds for some depth three circuits

Cited in

(26)

• Algebraic proof systems over formulas.
• Ulrich complexity
• Circuit and decision tree complexity of some number theoretic problems
• Affine projections of symmetric polynomials.
• Limitations of sums of bounded read formulas and ABPs
• Improved bounds on the an-complexity of \(O(1)\)-linear functions
• Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits
• Unifying known lower bounds via geometric complexity theory
• Arithmetic circuits: a chasm at depth 3
• A Selection of Lower Bounds for Arithmetic Circuits
• Uniform derandomization from pathetic lower bounds
• On the Expressive Power of Read-Once Determinants
• Lower bounds for depth-three arithmetic circuits with small bottom fanin
• Arithmetic circuits: the chasm at depth four gets wider
• scientific article; zbMATH DE number 1775446 (Why is no real title available?)
• Lower bounds for depth three arithmetic circuits with small bottom fanin
• The computational power of depth five arithmetic circuits
• A super-quadratic lower bound for depth four arithmetic circuits
• scientific article; zbMATH DE number 7561765 (Why is no real title available?)
• scientific article; zbMATH DE number 7204282 (Why is no real title available?)
• scientific article; zbMATH DE number 7250151 (Why is no real title available?)
• On the complexity of powering in finite fields
• Approaching the chasm at depth four
• Depth-3 arithmetic circuits over fields of characteristic zero
• A spectral theory for tensors
• New bounds for the ideal proof system in positive characteristic

This page was built for publication: Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1573765)