1. You are Here：

Full metadata record
DC FieldValueLanguage
dc.contributor.authorLu, Chi-Jenen_US
dc.contributor.authorTsai, Shi-Chunen_US
dc.contributor.authorWu, Hsin-Lungen_US
dc.date.accessioned2014-12-08T15:14:42Z-
dc.date.available2014-12-08T15:14:42Z-
dc.date.issued2007-02-12en_US
dc.identifier.issn0304-3975en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2006.10.009en_US
dc.identifier.urihttp://hdl.handle.net/11536/11136-
dc.description.abstractWe 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.isoen_USen_US
dc.subjectcomputational complexityen_US
dc.subjecthardness amplificationen_US
dc.subjectpseudorandom generatoren_US
dc.subjectNPen_US
dc.titleImproved hardness amplification in NPen_US
dc.typeArticleen_US
dc.identifier.doi10.1016/j.tcs.2006.10.009en_US
dc.identifier.journalTHEORETICAL COMPUTER SCIENCEen_US
dc.citation.volume370en_US
dc.citation.issue1-3en_US
dc.citation.spage293en_US
dc.citation.epage298en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000244214900020-
dc.citation.woscount3-
Appears in Collections:Articles


Files in This Item:

  1. 000244214900020.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.

Related Contents
Loading...