Improved bounds for reduction to depth 4 and depth 3

DOI10.1016/j.ic.2014.09.004zbMath1312.68093OpenAlexW1508771701MaRDI QIDQ2514141

Sébastien Tavenas

Publication date: 30 January 2015

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.09.004

zbMATH Keywords

parallelizationarithmetic circuit

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (15)

The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science ⋮ Equations for secant varieties of Chow varieties ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ The method of shifted partial derivatives cannot separate the permanent from the determinant ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Unnamed Item ⋮ Towards Optimal Depth Reductions for Syntactically Multilinear Circuits ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Unnamed Item ⋮ Lower bounds for matrix factorization

Cites Work

• Arithmetic circuits: the chasm at depth four gets wider
• Feasible arithmetic computations: Valiant's hypothesis
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Completeness and reduction in algebraic complexity theory
• Characterizing Valiant's algebraic complexity classes
• Arithmetic Circuits: A Chasm at Depth 3
• Fast Parallel Computation of Polynomials Using Few Processors
• Arithmetic Circuits: A survey of recent results and open questions
• Approaching the Chasm at Depth Four

This page was built for publication: Improved bounds for reduction to depth 4 and depth 3