The perceptron strikes back
- 10 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 286-291
- https://doi.org/10.1109/sct.1991.160270
Abstract
We show that every AC0predicate is computedby a low-degree probabilistic polynomial over thereals. We show that circuits composed of a symmetricgate at the root with AND-OR subcircuitsof constant depth can be simulated by probabilisticdepth-2 circuits with essentially the samesymmetric gate at the root and AND gates of smallfanin at the bottom. In particular, every languagerecognized by a depth-d AC0circuit is decidableby a probabilistic perceptron of size 2O(log4dn)...Keywords
This publication has 17 references indexed in Scilit:
- Randomized polynomials, threshold circuits, and the polynomial hierarchyPublished by Springer Nature ,2005
- Counting classes are at least as hard as the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- ON ACC and threshold circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Constant depth circuits, Fourier transform, and learnabilityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Random oracles separate PSPACE from the polynomial-time hierarchyInformation Processing Letters, 1987
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- Algebraic methods in the theory of lower bounds for Boolean circuit complexityPublished by Association for Computing Machinery (ACM) ,1987
- Almost optimal lower bounds for small depth circuitsPublished by Association for Computing Machinery (ACM) ,1986
- NP is as easy as detecting unique solutionsTheoretical Computer Science, 1986
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985