Počet záznamů: 1
A New Characterization of ACC(0) and Probabilistic CC0
- 1.
SYSNO ASEP 0352500 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A New Characterization of ACC(0) and Probabilistic CC0 Tvůrce(i) Hansen, A. K. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCIDZdroj.dok. Computational Complexity. - : Springer - ISSN 1016-3328
Roč. 19, č. 2 (2010), s. 211-234Poč.str. 24 s. Akce 24th Annual IEEE Conference on Computational Complexity Datum konání 15.07.2009-18.07.2009 Místo konání Paris Země FR - Francie Typ akce WRD Jazyk dok. eng - angličtina Země vyd. CH - Švýcarsko Klíč. slova bounded depth circuits ; counting circuits ; arithmetic circuits ; complexity classes Vědní obor RIV BA - Obecná matematika CEP GAP202/10/0854 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy IAA100190902 GA AV ČR - Akademie věd CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000278521500004 EID SCOPUS 77953538534 DOI 10.1007/s00037-010-0287-z Anotace 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.) Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1