Posted by: atri | September 19, 2007

Project 13: Codes in hardness amplification

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

  • Given a function f:X^n\rightarrow \mathbb{R} that is “hard” to compute on all inputs, can one define another function g:X^{n'}\rightarrow \mathbb{R} 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 n'=O(n).

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 g also computes the same function as f (though on larger number of inputs) or when both f and g lie in the same complexity class such as NP.

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


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: