Počet záznamů: 1
A New Characterization of ACC(0) and Probabilistic CC0
- 1.0352500 - MÚ 2011 RIV CH eng J - Článek v odborném periodiku
Hansen, A. K. - Koucký, Michal
A New Characterization of ACC(0) and Probabilistic CC0.
Computational Complexity. Roč. 19, č. 2 (2010), s. 211-234. ISSN 1016-3328. E-ISSN 1420-8954.
[24th Annual IEEE Conference on Computational Complexity. Paris, 15.07.2009-18.07.2009]
Grant CEP: GA ČR GAP202/10/0854; GA MŠMT(CZ) 1M0545; GA AV ČR IAA100190902
Výzkumný záměr: CEZ:AV0Z10190503
Klíčová slova: bounded depth circuits * counting circuits * arithmetic circuits * complexity classes
Kód oboru RIV: BA - Obecná matematika
Impakt faktor: 1.450, rok: 2010
http://link.springer.com/article/10.1007%2Fs00037-010-0287-z
Barrington, Straubing and 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 CC^0 circuits. In this work we show that the AND function can be computed by uniform probabilistic CC^0 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^0 can be computed by probabilistic CC^0 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 ACC^0=CC^0. We present a derandomization of probabilistic CC^0 circuits using AND and OR gates to obtain ACC^0 = AND /circ OR /circ CC^0 = OR /circ AND /circ CC^0. (AND and OR gates of sublinear fan-in suffice in non-uniform setting.)
Trvalý link: http://hdl.handle.net/11104/0191994
Název souboru Staženo Velikost Komentář Verze Přístup Koucky3.pdf 1 539.5 KB Vydavatelský postprint vyžádat
Počet záznamů: 1