A New Characterization of ACC(0) and Probabilistic CC0

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F10%3A00352500" target="_blank" >RIV/67985840:_____/10:00352500 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

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

Název v anglickém jazyce

A New Characterization of ACC(0) and Probabilistic CC0

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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)

Rok uplatnění

2010

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ů

Název periodika

Computational Complexity

ISSN

1016-3328

e-ISSN

—

Svazek periodika

19

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

24

Strana od-do

—

Kód UT WoS článku

000278521500004

EID výsledku v databázi Scopus

—