Počet záznamů: 1
A new characterization of ACC(0) and probabilistic CC0
- 1.
SYSNO ASEP 0336102 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A new characterization of ACC(0) and probabilistic CC0 Tvůrce(i) Hansen, K.A. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCIDZdroj.dok. Proceedings of the 24th Annual IEEE Conference on Computational Complexity. - Los Alamitos : IEEE Computer Society, 2009 - ISSN 1093-0159 - ISBN 978-0-7695-3717-7 Rozsah stran s. 27-34 Poč.str. 8 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. US - Spojené státy americké Klíč. slova bounded depth circuits ; counting circuits Vědní obor RIV BA - Obecná matematika CEP GP201/07/P276 GA ČR - Grantová agentura ČR IAA100190902 GA AV ČR - Akademie věd 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000273015300004 Anotace 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 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, we 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 /circ OR /circ CC0 = OR /circ AND /circ CC0. AND and OR gates of sublinear fan-in suffice. Both these results hold for uniform as well as non-uniform circuit classes. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1