A New Characterization of ACC(0) and Probabilistic CC0

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

A New Characterization of ACC(0) and Probabilistic CC0

Original language description

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

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2010

Confidentiality

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

Name of the periodical

Computational Complexity

ISSN

1016-3328

e-ISSN

—

Volume of the periodical

19

Issue of the periodical within the volume

2

Country of publishing house

CH - SWITZERLAND

Number of pages

24

Pages from-to

—

UT code for WoS article

000278521500004

EID of the result in the Scopus database

—