Constant depth circuits, Fourier transform, and learnability
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 574-579
- https://doi.org/10.1109/sfcs.1989.63537
Abstract
Boolean functions in AC/sup O/ are studied using the harmonic analysis of the cube. The main result is that an AC/sup O/ Boolean function has almost all of its power spectrum on the low-order coefficients. This result implies the following properties of functions in AC/sup O/: functions in AC/sup O/ have low average sensitivity; they can be approximated well be a real polynomial of low degree; they cannot be pseudorandom function generators and their correlation with any polylog-wide independent probability distribution is small. An O(n/sup polylog(/ /sup sup)/ /sup (n)/)-time algorithm for learning functions in AC/sup O/ is obtained. The algorithm observed the behavior of an AC/sup O/ function on O(n/sup polylog/ /sup (n)/) randomly chosen inputs and derives a good approximation for the Fourier transform of the function. This allows it to predict with high probability the value of the function on other randomly chosen inputs.Keywords
This publication has 13 references indexed in Scilit:
- A spectral lower bound technique for the size of decision trees and two-level AND/OR circuitsIEEE Transactions on Computers, 1990
- Hardness vs. randomnessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- The influence of variables on Boolean functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Learning decision listsMachine Learning, 1987
- Generic oracles and oracle classesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Algebraic methods in the theory of lower bounds for Boolean circuit complexityPublished by Association for Computing Machinery (ACM) ,1987
- How to construct random functionsJournal of the ACM, 1986
- Deterministic simulation of probabilistic constant depth circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- A theory of the learnableCommunications of the ACM, 1984
- Parity, circuits, and the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981