• DocumentCode
    2113742
  • Title

    VC dimension in circuit complexity

  • Author

    Koiran, Pascal

  • Author_Institution
    Lab. LIP-IMAG, Ecole Normale Superieure de Lyon, France
  • fYear
    1996
  • fDate
    24-27 May 1996
  • Firstpage
    81
  • Lastpage
    85
  • Abstract
    The main result of this paper is a Ω(n1/4) lower bound on the size of a sigmoidal circuit computing a specific AC2 0 function. This is the first lower bound for the computation model of sigmoidal circuits with unbounded weights. We also give upper and lower bounds for the same function in a few other computation models: circuits of AND/OR gates, threshold circuits, and circuits of piecewise-rational gates
  • Keywords
    computational complexity; logic circuits; AC20 function; AND/OR gates; VC dimension; circuit complexity; computation models; lower bound; piecewise-rational gates; sigmoidal circuits; threshold circuits; unbounded weights; Circuits; Complexity theory; Computational modeling; Input variables; Machine learning; Mathematical model; Upper bound; Virtual colonoscopy;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
  • Conference_Location
    Philadelphia, PA
  • Print_ISBN
    0-8186-7386-9
  • Type

    conf

  • DOI
    10.1109/CCC.1996.507671
  • Filename
    507671
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2113742