Number of the records: 1

A New Characterization of ACC(0) and Probabilistic CC0

SYSNO ASEP	0352500
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	A New Characterization of ACC(0) and Probabilistic CC0
Author(s)	Hansen, A. K. (DK) Koucký, Michal (MU-W)_{RID, SAI, ORCID}
Source Title	Computational Complexity. - : Springer - ISSN 1016-3328 Roč. 19, č. 2 (2010), s. 211-234
Number of pages	24 s.
Action	24th Annual IEEE Conference on Computational Complexity
Event date	15.07.2009-18.07.2009
VEvent location	Paris
Country	FR - France
Event type	WRD
Language	eng - English
Country	CH - Switzerland
Keywords	bounded depth circuits ; counting circuits ; arithmetic circuits ; complexity classes
Subject RIV	BA - General Mathematics
R&D Projects	GAP202/10/0854 GA ČR - Czech Science Foundation (CSF)
	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
	IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000278521500004
EID SCOPUS	77953538534
DOI	10.1007/s00037-010-0287-z
Annotation	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 be computed 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.)
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1