Informally speaking, hardness amplification is the following problem in complexity theory.

• Given a function that is “hard” to compute on all inputs, can one define another function such that is it “hard” to compute even on some fraction of the inputs?

In the above, the notion of hardness generally means that the functions cannot be computed efficiently (either via a Turing machine or a circuit). Also ideally, we would like .

A natural question to ask is why is the above problem interesting? One of the critiques of “traditional/usual” hardness results in complexity theory is that they hold for worst-case inputs. What harndess amplification is trying to do is to show hardness of functions on the average. Some interesting special cases of the problem is when also computes the same function as (though on larger number of inputs) or when both and lie in the same complexity class such as .

Some of the best known hardness amplification results use list decoding. A quick starting point will be the mini-survey by Guruswami titled List Decoding in Average-Case Complexity and Pseudorandomness (Section II and the references therein). For a more recent paper on this topic take a look at paper by Jaiswal, Impagliazzo and Kabanets titled Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification (FOCS06).

Your response: