Number of the records: 1

Amplifying lower bounds by means of self-reducibility

SYSNO ASEP	0352511
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Amplifying lower bounds by means of self-reducibility
Author(s)	Allender, E. (US) Koucký, Michal (MU-W)_{RID, SAI, ORCID}
Source Title	Journal of the ACM. - : Association for Computing Machinery - ISSN 0004-5411 Roč. 57, č. 3 (2010), s. 1-36
Number of pages	36 s.
Language	eng - English
Country	US - United States
Keywords	Circuit Complexity ; Lower Bounds ; Natural Proofs ; Self-Reducibility ; Time-Space Tradeoffs
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	000277058400003
EID SCOPUS	77950344196
DOI	10.1145/1706591.1706594
Annotation	We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+eps} for every eps> 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC^1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+eps_d} . If one were able to improve this lower bound to show that there is some constant eps> 0 (independent of the depth d) such that every TC^0 circuit family recognizing BFE has size at least n^{1+eps}, then it would follow that TC^0 /not= NC^1.
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