Improved hardness amplification in NP

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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 languageEnglish
Pages (from-to)293-298
Number of pages6
JournalTheoretical Computer Science
Volume370
Issue number1-3
DOIs
StatePublished - 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