Authors: Richard Beigel and Jun Tarui
Abstract: We show that every language L in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and nlogO(1)n AND gates of fan-in logO(1)n at the leaves, or equivalently, there exist polynomials pn(x) over Z of degree logO(1)n and with coefficients of magnitude nlogO(1)n and functions hn : Z -> {0,1} such that for each n and each x in {0,1}n, χL(x)=hn(pn(x)). This improves an earlier result of Yao. We also analyze and improve modulus-amplifying polynomials constructed by Toda and Yao.