Improved hardness amplification in NP

doi:10.1016/j.tcs.2006.10.009

完整後設資料紀錄

DC 欄位	值	語言
dc.contributor.author	Lu, Chi-Jen	en_US
dc.contributor.author	Tsai, Shi-Chun	en_US
dc.contributor.author	Wu, Hsin-Lung	en_US
dc.date.accessioned	2014-12-08T15:14:42Z	-
dc.date.available	2014-12-08T15:14:42Z	-
dc.date.issued	2007-02-12	en_US
dc.identifier.issn	0304-3975	en_US
dc.identifier.uri	http://dx.doi.org/10.1016/j.tcs.2006.10.009	en_US
dc.identifier.uri	http://hdl.handle.net/11536/11136	-
dc.description.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(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.	en_US
dc.language.iso	en_US	en_US
dc.subject	computational complexity	en_US
dc.subject	hardness amplification	en_US
dc.subject	pseudorandom generator	en_US
dc.subject	NP	en_US
dc.title	Improved hardness amplification in NP	en_US
dc.type	Article	en_US
dc.identifier.doi	10.1016/j.tcs.2006.10.009	en_US
dc.identifier.journal	THEORETICAL COMPUTER SCIENCE	en_US
dc.citation.volume	370	en_US
dc.citation.issue	1-3	en_US
dc.citation.spage	293	en_US
dc.citation.epage	298	en_US
dc.contributor.department	資訊工程學系	zh_TW
dc.contributor.department	Department of Computer Science	en_US
dc.identifier.wosnumber	WOS:000244214900020	-
dc.citation.woscount	3	-
顯示於類別：	期刊論文

文件中的檔案：

000244214900020.pdf

若為 zip 檔案，請下載檔案解壓縮後，用瀏覽器開啟資料夾中的 index.html 瀏覽全文。