Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-062 | 11th June 2008 00:00

Arithmetic Circuits: A Chasm at Depth Four

RSS-Feed




TR08-062
Authors: Manindra Agrawal, V Vinay
Publication: 12th June 2008 21:02
Downloads: 4180
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint