Počet záznamů: 1

A new characterization of ACC(0) and probabilistic CC0

  1. 1.
    0336102 - MU-W 2010 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
    Hansen, K.A. - Koucký, Michal
    A new characterization of ACC(0) and probabilistic CC0.
    Proceedings of the 24th Annual IEEE Conference on Computational Complexity. Los Alamitos: IEEE Computer Society, 2009, s. 27-34. ISBN 978-0-7695-3717-7. ISSN 1093-0159.
    [24th Annual IEEE Conference on Computational Complexity. Paris (FR), 15.07.2009-18.07.2009]
    Grant CEP: GA ČR GP201/07/P276; GA AV ČR IAA100190902; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: bounded depth circuits * counting circuits
    Kód oboru RIV: BA - Obecná matematika

    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.
    Trvalý link: http://hdl.handle.net/11104/0180415
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky.pdf1343.6 KBVydavatelský postprintvyžádat