Title :
ON ACC and threshold circuits
Author :
Yao, Andrew Chi-Chih
Author_Institution :
Dept. of Comput. Sci., Princeton Univ., NJ, USA
Abstract :
It is proved that any language in ACC can be approximately computed by two-level circuits of size 2 raised to the (log n) k power, with a symmetric-function gate at the top and only AND gates on the first level. This implies that any language in ACC can be recognized by depth-3 threshold circuits of that size. This result gives the first nontrivial upper bound on the computing power of ACC circuits
Keywords :
combinatorial switching; formal languages; threshold logic; ACC; AND gates; computing power; depth-3 threshold circuits; language; symmetric-function gate; threshold circuits; two-level circuits; Character recognition; Circuit theory; Computer science; Frequency selective surfaces; Galois fields; Input variables; Polynomials; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
DOI :
10.1109/FSCS.1990.89583
