TY - JOUR

T1 - On the complexity of hardness amplification

AU - Lu, Chi Jen

AU - Tsai, Shi-Chun

AU - Wu, Hsin Lung

PY - 2008/10/9

Y1 - 2008/10/9

N2 - For δ ∈ (0, 1) and k, n ∈ N, we study the task of transforming a hard function f: {0, 1}n → {0, 1}, 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. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2o (kk1/d) or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth) for any δ ∈ (0, 1). This extends the result of Viola, which only works when (1 - δ)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f′, even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Ω (k log (1/δ)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1 - δ)/2 = 2-n. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

AB - For δ ∈ (0, 1) and k, n ∈ N, we study the task of transforming a hard function f: {0, 1}n → {0, 1}, 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. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2o (kk1/d) or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth) for any δ ∈ (0, 1). This extends the result of Viola, which only works when (1 - δ)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f′, even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Ω (k log (1/δ)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1 - δ)/2 = 2-n. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

KW - Complexity theory

KW - Computational complexity

KW - Construction industry

KW - Decoding

KW - Encoding

KW - Hardness amplification

KW - Integrated circuit modeling

KW - List-decodable code

KW - Noise

KW - Pseudorandom generator

KW - Transforms

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

U2 - 10.1109/TIT.2008.928988

DO - 10.1109/TIT.2008.928988

M3 - Article

AN - SCOPUS:54749138124

VL - 54

SP - 4575

EP - 4586

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 10

ER -