Title :
Arithmetic Circuits: A Chasm at Depth Four
Author :
Agrawal, Manindra ; Vinay, V.
Author_Institution :
Indian Inst. of Technol., Kanpur
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.
Keywords :
circuit complexity; circuit testing; digital arithmetic; logic testing; multiplying circuits; arithmetic circuits; complete black-box derandomization; exponential lower bounds; identity testing problem; multiplication gates; Circuit testing; Computer science; Costs; Digital arithmetic; Galois fields; Information systems; Polynomials; Size measurement; Arithmetic Circuits; Circuit Complexity; Computational Complexity; Depth Reduction; Identity Testing; Lower Bounds;
Conference_Titel :
Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on
Conference_Location :
Philadelphia, PA
Print_ISBN :
978-0-7695-3436-7
DOI :
10.1109/FOCS.2008.32