• DocumentCode
    1632571
  • Title

    Learnability beyond AC0

  • Author

    Jackson, Jeffrey C. ; Klivans, Adam R. ; Servedio, Rocco A.

  • Author_Institution
    Duquesne Univ., Pittsburgh, PA, USA
  • fYear
    2002
  • fDate
    6/24/1905 12:00:00 AM
  • Firstpage
    16
  • Lastpage
    16
  • Abstract
    We give an algorithm for learning a more expressive circuit class than the class AC0 considered by Linial et al. (1993) and Kharitonov (1993). The new algorithm learns constant-depth AND/OR/NOT circuits augmented with (a limited number of) majority gates. Our main positive result for these circuits is stated informally
  • Keywords
    circuit complexity; learning (artificial intelligence); logic gates; AND circuits; Boolean cube; NOT circuits; OR circuits; circuit class; circuit complexity; constant-depth circuits; cryptographic assumption; integer factorization; learning; majority gates; uniformly distributed random examples; Boosting; Circuits; Complexity theory; Computational complexity; Cryptography; Fourier transforms; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
  • Conference_Location
    Montreal, Que.
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-1468-5
  • Type

    conf

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