### Abstract

We study the problem of hardness amplification in NP. We prove that if there is a balanced function in NP such that any circuit of size s (n) = 2^{Ω (n)} fails to compute it on a 1 / poly (n) fraction of inputs, then there is a function in NP such that any circuit of size s^{′} (n) fails to compute it on a 1 / 2 - 1 / s^{′} (n) fraction of inputs, with s^{′} (n) = 2^{Ω (n2 / 3)}. This improves the result of Healy et al. (STOC'04), which only achieves s^{′} (n) = 2^{Ω (n1 / 2)} for the case with s (n) = 2^{Ω (n)}.

Original language | English |
---|---|

Pages (from-to) | 293-298 |

Number of pages | 6 |

Journal | Theoretical Computer Science |

Volume | 370 |

Issue number | 1-3 |

DOIs | |

State | Published - 12 Feb 2007 |

### Keywords

- Computational complexity
- Hardness amplification
- NP
- Pseudorandom generator

## Fingerprint Dive into the research topics of 'Improved hardness amplification in NP'. Together they form a unique fingerprint.

## Cite this

Lu, C. J., Tsai, S-C., & Wu, H. L. (2007). Improved hardness amplification in NP.

*Theoretical Computer Science*,*370*(1-3), 293-298. https://doi.org/10.1016/j.tcs.2006.10.009