TY - GEN

T1 - Impossibility results on weakly black-box hardness amplification

AU - Lu, Chi Jen

AU - Tsai, Shi-Chun

AU - Wu, Hsin Lung

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38149126222&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-74240-1_35

DO - 10.1007/978-3-540-74240-1_35

M3 - Conference contribution

AN - SCOPUS:38149126222

SN - 9783540742395

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 400

EP - 411

BT - Fundamentals of Computation Theory - 16th International Symposium, FCT 2007, Proceedings

Y2 - 27 August 2007 through 30 August 2007

ER -