Title :
Learnability beyond AC0
Author :
Jackson, Jeffrey C. ; Klivans, Adam R. ; Servedio, Rocco A.
Author_Institution :
Duquesne Univ., Pittsburgh, PA, USA
fDate :
6/24/1905 12:00:00 AM
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;
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-7695-1468-5
DOI :
10.1109/CCC.2002.1004335
