DocumentCode
1593938
Title
Arithmetic Circuits: A Chasm at Depth Four
Author
Agrawal, Manindra ; Vinay, V.
Author_Institution
Indian Inst. of Technol., Kanpur
fYear
2008
Firstpage
67
Lastpage
75
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2008. FOCS '08. IEEE 49th Annual IEEE Symposium on
Conference_Location
Philadelphia, PA
ISSN
0272-5428
Print_ISBN
978-0-7695-3436-7
Type
conf
DOI
10.1109/FOCS.2008.32
Filename
4690941
Link To Document