Arithmetic Circuits: A Chasm at Depth Four

We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of identity testing problem for depth four circuits with multiplication gates of small fanin implies a nearly complete derandomization of general identity testing.

Authors

• Manindra Agrawal
• V. Vinay

Keywords

• Circuit testing
• Polynomials
• Digital arithmetic
• Computer science
• Information systems
• Galois fields
• Size measurement
• Costs
• Arithmetic Circuits
• Lower Bound
• Identification Test
• Multiple Gates
• Polynomial Of Degree
• Sum Of Products
• Finite Field
• Monomial
• Circuit Size
• Left Child
• Computational Complexity
• Depth Reduction
• Lower Bounds
• Circuit Complexity
• Identity Testing