On ACC

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 n/sup polylog/(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 n/sup polylog/(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. >

Authors

• Richard Beigel
• Jun Tarui

Keywords

• Complexity theory
• Polynomials
• Computer science
• Boolean functions
• Circuit analysis computing
• Galois fields
• Wires
• Decision Tree
• Proof Of Theorem
• Power Series
• Nearest Integer
• Symmetric Function
• Boolean Variable
• Polynomial Ring
• Random Bits
• Circuit Size
• Commutative Algebra
• Top Gate
• Department Of Computer Science
• OR Gate
• NOT Gate
• Bottom Gate