Name
Abstract | ||
|---|---|---|
. Barrington, Straubing & Thérien (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 CC0 circuits. In this work we show that the And function can be computed by uniform probabilistic CC0 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 ACC0 can be computed by probabilistic CC0 circuits that use only O(log n) random bits. Thus, if one were able to derandomize such circuits, one would obtain a collapse of circuit classes giving
ACC0 = CC0. We present a derandomization of probabilistic CC0 circuits using And and Or gates to obtain ACC0 = And ο Or ο CC0 = Or ο And ο CC0. (And and Or gates of sublinear fan-in suffice in non-uniform setting.)
Both these results hold for uniform as well as non-uniform circuit classes. For non-uniform circuits we obtain the stronger
conclusion that ACC0 = rand – ACC0 = rand – CC0 = rand(log n)– CC0, i.e., probabilistic ACC0 circuits can be simulated by probabilistic CC0 circuits using only O(log n) random bits.
As an application of our results we obtain a characterization of ACC0 by constant width planar nondeterministic branching programs, improving a previous characterization for the quasi-polynomial
size setting. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00037-010-0287-z | Computational Complexity - Selected papers from the 24th Annual IEEE Conference on Computational Complexity (CCC 2009) |
Keywords | DocType | Volume |
branching program,boolean circuits | Journal | 19 |
Issue | ISSN | Citations |
2 | 1420-8954 | 8 |
PageRank | References | Authors |
0.50 | 31 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kristoffer Arnsfelt Hansen | 1 | 176 | 21.40 |
| Michal Koucky | 2 | 77 | 6.06 |