Perceptrons, PP, and the polynomial hierarchy

E. Allender, A note on the power of threshold circuits. InProceedings of the 30th Ann. Symp. Found. Comput. Sci., 1989, 580?584.

E. Allender and U. Hertrampf, Depth reduction for circuits of unbounded fanin.Inform. and Comput. 108 (1994). To appear.

J. Aspnes, R. Beigel, M. Furst, and S. Rudich, The expressive power of voting polynomials. InProceedings of the 23rd Ann. ACM Symp. Theor. Comput., 1991, 402?409. A revised version is to appear inCombinatorica.

R. Beigel and J. Tarui, On ACC. This Journal.

R. Beigel, L. A. Hemachandra, andG. Wechsung, Probabilistic polynomial time is closed under parity reductions.Inform. Process. Lett. 37(2) (1991a), 91?94.

R. Beigel, N. Reingold, and D. Spielman, The perceptron strikes back. InProceedings of the 6th Ann. Conf. Structure in Complexity Theory, 1991b, 286?291.

R. Beigel, N. Reingold, and D. Spielman, PP is closed under intersection.J. Comput. System Sci. 48 (1994). To appear.

S. R. Buss andL. E. Hay, On truth table reducibility to SAT.Inform. and Comput. 91(1) (1991), 86?102.

E. W. Cheney,Approximation Theory. McGraw-Hill, 1966.

H. Ehlich andK. Zeller, Schwankung von polynomen zwischen gitterpunkten.Math. Z. 86 (1964), 41?44.

B. Fu, Separating PH from PP by relativization.Acta Math. Sinica 8(3) (1992), 329?336.

M. Furst, J. B. Saxe, andM. Sipser, Parity, circuits, and the polynomial-time hierarchy.Math. Systems Theory 17(1) (1984), 13?27.

T. Gundermann, N. Nasser, and G. Wechsung, A survey of counting classes. InProceedings of the 5th Ann. Conf. Structure in Complexity Theory. IEEE Computer Society Press, 1990, 140?153.

L. Hemachandra andG. Wechsung, On the power of probabilistic polynomial time: $$P^{NP[log]} \subseteq PP$$ . Technical Report CUCS-372-88, Columbia Dept. of Computer Science, New York, NY, 1988.

G. G. Lorentz,Approximation of Functions. Holt, Rinehart and Winston, New York, 1966.

M. L. Minsky andS. A. Papert,Perceptrons. MIT Press, Cambridge, MA, 1988. Expanded version of the original 1968 edition.

G. Pólya andG. Szegö,Problems and Theorems in Analysis. Springer-Verlag, Berlin, 1972.

T. J. Rivlin andE. W. Cheney, A comparison of uniform approximations on an interval and a finite subset thereof.SIAM Numer. Anal. 3(2) (1966), 311?320.

J. Tarui, Probabilistic polynomials, AC0 functions, and the polynomial-time hierarchy.Theoret. Comput. Sci. 113 (1993), 167?183.

S. Toda, PP is as hard as the polynomial-time hierarchy.SIAM J. Comput. 20(5) (1991), 865?877.

S. Toda andM. Ogiwara, Counting classes are at least as hard as the polynomial-time hierarchy.SIAM J. Comput. 21(2) (1992), 316?328.

A. C.-C. Yao, On ACC and threshold circuits. InProceedings of the 31st Ann. Symp. Found. Comput. Sci., 1990, 619?627.