scientific article; zbMATH DE number 1775446

zbMath1028.68069MaRDI QIDQ4542578

Marek Karpinski, Dima Yu. Grigoriev

Publication date: 1 August 2002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

first exponential lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (23)

Affine projections of symmetric polynomials. ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ Ulrich complexity ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ 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 ⋮ Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ 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: