Impossibility results on weakly black-box hardness amplification

Chi Jen Lu*, Shi-Chun Tsai, Hsin Lung Wu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

We study the task of hardness amplification which transforms a hard function into a harder one. It is known that in a high complexity class such as exponential time, one can convert worst-case hardness into average-case hardness. However, in a lower complexity class such as NP or sub-exponential time, the existence of such an amplification procedure remains unclear. We consider a class of hardness amplifications called weakly black-box hardness amplification, in which the initial hard function is only used as a black box to construct the harder function. We show that if an amplification procedure in TIME(t) can amplify hardness beyond an O(t) factor, then it must basically embed in itself a hard function computable in TIME(t). As a result, it is impossible to have such a hardness amplification with hardness measured against TIME(t). Furthermore, we show that, for any k ∈ ℕ, if an amplification procedure in ΣkP can amplify hardness beyond a polynomial factor, then it must basically embed a hard function in ΣkP. This in turn implies the impossibility of having such hardness amplification with hardness measured against ΣkP/poly.

Original languageEnglish
Title of host publicationFundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings
Pages400-411
Number of pages12
DOIs
StatePublished - 1 Dec 2007
Event16th International Symposium on Fundamentals of Computation Theory, FCT 2007 - Budapest, Hungary
Duration: 27 Aug 200730 Aug 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4639 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Symposium on Fundamentals of Computation Theory, FCT 2007
CountryHungary
CityBudapest
Period27/08/0730/08/07

Fingerprint Dive into the research topics of 'Impossibility results on weakly black-box hardness amplification'. Together they form a unique fingerprint.

Cite this