ON ACC and threshold circuits

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)/sup 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>