Amplifying lower bounds by means of self-reducibility
Result description
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 circuitsof 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.
Keywords
Circuit ComplexityLower BoundsNatural ProofsSelf-ReducibilityTime-Space Tradeoffs
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Amplifying lower bounds by means of self-reducibility
Original language description
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 circuitsof 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.
Czech name
—
Czech description
—
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
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)
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2010
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
Name of the periodical
Journal of the ACM
ISSN
0004-5411
e-ISSN
—
Volume of the periodical
57
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
36
Pages from-to
—
UT code for WoS article
000277058400003
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BA - General mathematics
Year of implementation
2010