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 :
بازگشت