**Authors:** Richard Beigel, Jun Tarui, and Seinosuke Toda

**Abstract:**
Let SYM^{+} denote the class of Boolean functions computable
by depth-two size-*n*^{logO(1)n}
circuits with a symmetric-function gate at the root and AND gates of
fan-in log^{O(1)}*n* at the next level, or equivalently,
the class of Boolean functions *f* such that
*f*(*x*_{1}, ... , *x*_{n})
can be expressed as
*f*(*x*_{1}, ... , *x*_{n}) =
*h*_{n}(*p*_{n}(*x*_{1}, ... , *x*_{n}))
for some polynomial *p*_{n} over Z of
degree log^{O(1)}*n* and norm (the sum of the absolute
values of its coefficients)
*n*^{logO(1)n} and some function
*h*_{n} : Z -> {0,1}^{+}_{m} gates for some fixed
*m*.

In this paper, we consider augmenting the power of ACC circuits by
allowing randomness and allowing an exact-threshold gate as the output
gate (an exact-threshold gate outputs 1 if exactly *k* of its inputs
are 1, where *k* is a parameter; it outputs 0 otherwise), and show
that every Boolean function computed by this kind of augmented ACC
circuits is still in SYM^{+}.

Showing that some ``natural'' function *f* does not belong to the
class ACC remains an open problem in circuit complexity, and the
result that ^{+}^{+} in terms of polynomials, which are
perhaps easier to analyze than circuits, and showing that *f* is
not in SYM^{+}. Our new result and proof techniques suggest
that the possibility that SYM^{+} contains even more Boolean
functions than we currently know should also be kept in mind and
explored.

By a well-known connection (Furst & Saxe & Sipser, MST '84), we also obtain new results about some classes related to the polynomial-time hierarchy.