On the complexity of hardness amplification

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

*Corresponding author for this work

Research output: Contribution to journalConference article

8 Scopus citations

Abstract

We study the task of transforming a hard function f, with which any small circuit disagrees on (1 - δ) /2 fraction of the input, into a harder function f′, with which any small circuit disagrees on (1 - δk)/2 fraction of the input, for δ ε(0,1) and k ε N. We show that this process cannot be carried out in a black-box way by a circuit of depth d and size 2o(k1/d) or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth). In particular, for k = 2 Ω(n), such hardness amplification cannot be done in ATIME(O(1), 2o(n)). Therefore, hardness amplification in general requires a high complexity. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently non-uniform in the following sense. Given as an oracle any algorithm which agrees with f′ on (1 - δk)/2 fraction of the input, we still need an additional advice of length Ω(k log(1/δ)) in order to compute f correctly on (1 - δ)/2 fraction of the input. Therefore, to guarantee the hardness, even against uniform machines, of the function f′, one has to start with a function f which is hard against non-uniform circuits. Finally, we derive similar lower bounds for any black-box construction of pseudorandom generators from hard functions.

Original languageEnglish
Pages (from-to)170-182
Number of pages13
JournalProceedings of the Annual IEEE Conference on Computational Complexity
DOIs
StatePublished - 16 Nov 2005
Event20th Annual IEEE Conference on Computational Complexity - San Jose, CA, United States
Duration: 11 Jun 200515 Jun 2005

Fingerprint Dive into the research topics of 'On the complexity of hardness amplification'. Together they form a unique fingerprint.

  • Cite this