PSEUDORANDOM GENERATORS AND LEARNING ALGORITHMS FOR AC
Eera Sitharam · 1995
For any AC ~ function f of n bits, there is a poiynomial p such that any p(logn)-wise decomposable distribution f. tn other words, f cannot distinguish between the pseudorandom strings in the distribution and truly random strings. The polynomial p depends only o~ the size and depth of the circuit computing f. This subsumes and extends the class of distributions that were pre- viously known to fool AC ~ functions, and partially answers an open question posed by Linial and Nisan in 1990, as to whether every poly- log-wise independent distribution fools AC ~ functions or not. Each polylog-wise decomposable distribution serves as a fixed train- ing set of examples for learning (approximately interpolating) all AC ~ functions computed by circuits of some fixed depth and size. Further- more, small, natural distributions (training sets) exist that yield de- terministic learning algorithms that run in time O(2 p~176 for AC 0 functions, where the degree of the polylog depends on the size and depth of the circuit to be learnt. This improves on the randomized algorithms with the same time complexity given, for example, by Linial et al. in 1989, where the exam- ples for the training set are picked randomly from specific distributions.