Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

A new characterization of ACC(0) and probabilistic CC0

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F09%3A00336102" target="_blank" >RIV/67985840:_____/09:00336102 - isvavai.cz</a>

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    A new characterization of ACC(0) and probabilistic CC0

  • Popis výsledku v původním jazyce

    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 becomputed 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 thatuse 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.

  • Název v anglickém jazyce

    A new characterization of ACC(0) and probabilistic CC0

  • Popis výsledku anglicky

    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 becomputed 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 thatuse 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.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    BA - Obecná matematika

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Ostatní

  • Rok uplatnění

    2009

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    Proceedings of the 24th Annual IEEE Conference on Computational Complexity

  • ISBN

    978-0-7695-3717-7

  • ISSN

  • e-ISSN

  • Počet stran výsledku

    8

  • Strana od-do

  • Název nakladatele

    IEEE Computer Society

  • Místo vydání

    Los Alamitos

  • Místo konání akce

    Paris

  • Datum konání akce

    15. 7. 2009

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku

    000273015300004