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

DOI10.1007/s002009900021zbMath1040.68045OpenAlexW1979337672MaRDI QIDQ1573765

Alexander A. Razborov, Dima Yu. Grigoriev

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)

Related Items (19)

Affine projections of symmetric polynomials. ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Uniform derandomization from pathetic lower bounds ⋮ Ulrich complexity ⋮ On the Expressive Power of Read-Once Determinants ⋮ Algebraic proof systems over formulas. ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ Arithmetic circuits: the chasm at depth four gets wider ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ A spectral theory for tensors ⋮ Unnamed Item ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Approaching the Chasm at Depth Four ⋮ Circuit and decision tree complexity of some number theoretic problems ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Limitations of sums of bounded read formulas and ABPs

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