• 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