A New Characterization of ACC^0 and Probabilistic CC^0

Barrington, Straubing and Therien (1990) conjectured that the Boolean AND function can not be computed by polynomial size constant depth circuits built from modular counting gates, i.e., by CC⁰ circuits. In this work we show that the AND function can be computed by uniform probabilistic CC⁰ circuits that use only O(log n) random bits. This may be viewed as evidence contrary to the conjecture. As a consequence of our construction we get that all of ACC⁰ can be computed by probabilistic CC⁰ circuits that use only O(log n) random bits. Thus, if one were able to derandomize such circuits, we would obtain a collapse of circuit classes giving ACC⁰=CC⁰. We present a derandomization of probabilistic CC⁰ circuits using AND and OR gates to obtain ACC⁰ = AND o OR o CC⁰ = OR o AND o CC⁰. AND and OR gates of sublinear fan-in suffice. Both these results hold for uniform as well as non-uniform circuit classes. For non-uniform circuits we obtain the stronger conclusion that ACC⁰ = rand-ACC⁰ = rand-CC⁰ = rand(log n)-CC⁰, i.e., probabilistic ACC⁰ circuits can be simulated by probabilistic CC⁰ circuits using only O(log n) random bits. As an application of our results we obtain a characterization of ACC⁰ by constant width planar nondeterministic branching programs, improving a previous characterization for the quasipolynomial size setting.