Improved hardness amplification in NP
檔案
- 000244214900020.pdf (229.3 KB, Adobe PDF)
日期
2007-02-12
類型
系所
期刊名稱
THEORETICAL COMPUTER SCIENCE
卷期與頁次
第 370 卷第 1-3 期,頁 293–298
ISSN
0304-3975
語言
英文
摘要
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(Omega(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(Omega(n2/13)). This improves the result of Healy et al. (STOC'04), which only achievess s' (n) = 2(Omega(n1/2)) for the case with s(n) = 2(Omega(n)). (c) 2006 Elsevier B.V. All rights reserved.