Arithmetic circuits: a chasm at depth four

Agrawal, Manindra ; Vinay, V. (2008) Arithmetic circuits: a chasm at depth four Proceedings - Annual Symposium on Foundations of Computer Science . pp. 67-75. ISSN 0272-5428

PDF - Author Version

Official URL:

Related URL:


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.

Item Type:Article
Source:Copyright of this article belongs to IEEE.
ID Code:92016
Deposited On:26 May 2012 13:58
Last Modified:19 May 2016 05:36

Repository Staff Only: item control page