Title :
On ACC [circuit complexity]
Author :
Beigel, Richard ; Tarui, Jun
Author_Institution :
Yale Univ., New Haven, CT, USA
Abstract :
It has been shown by A. Yao (1990) that every language in ACC is recognized by a sequence of depth-2 probabilistic circuits with a symmetric gate at the root and npolylog(n) AND gates of fan-in polylog (n) at the leaves. The authors simplify Yao´s proof and strengthen his results: every language in ACC is recognized by a sequence of depth-2 deterministic circuits with a symmetric gate at the root and npolylog(n) AND gates of fan-in polylog(n) at the leaves. They also analyze and improve modulus-amplifying polynomials constructed by S. Toda (1989) and Yao: this yields smaller circuits in Yao´s and the present results on ACC
Keywords :
computational complexity; formal languages; logic circuits; threshold logic; ACC; AND gates; depth-2 deterministic circuits; depth-2 probabilistic circuits; fan-in; language; leaves; modulus-amplifying polynomials; root; symmetric gate; Boolean functions; Circuit analysis computing; Complexity theory; Computer science; Galois fields; Polynomials; Wires;
Conference_Titel :
Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Conference_Location :
San Juan
Print_ISBN :
0-8186-2445-0
DOI :
10.1109/SFCS.1991.185449
