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