A new characterization of ACC(0) and probabilistic CC0
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
A new characterization of ACC(0) and probabilistic CC0
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 24th Annual IEEE Conference on Computational Complexity
ISBN
978-0-7695-3717-7
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
—
Publisher name
IEEE Computer Society
Place of publication
Los Alamitos
Event location
Paris
Event date
Jul 15, 2009
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000273015300004