Show simple item record

dc.contributor.authorHealy, Alexander
dc.contributor.authorVadhan, Salil
dc.contributor.authorViola, Emanuele
dc.date.accessioned2019-10-03T17:42:15Z
dc.date.issued2006
dc.identifier.citationHealy, Alexander, Salil Vadhan, and Emanuele Viola. 2006. “Using Nondeterminism to Amplify Hardness.” SIAM Journal on Computing 35 (4): 903–31. https://doi.org/10.1137/s0097539705447281.
dc.identifier.issn0097-5397
dc.identifier.issn1095-7111
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:41467485*
dc.description.abstractWe revisit the problem of hardness amplification in NP, as recently studied by O'Donnell [J. Comput. System Sci., 69 (2004), pp. 68-94]. We prove that if NP has a balanced function f such that any circuit of size s(n) fails to compute f on a 1/poly(n) fraction of inputs, then NP has a function f' such that any circuit of size s'(n) = s(root n)(Omega(1)) fails to compute f' on a 1/2 - 1/s' (n) fraction of inputs. In particular,1. if s(n) = n(omega(1)), we amplify to hardness 1/ 2 - 1/n(omega(1));2. if s(n) = 2(n Omega(1)), we amplify to hardness 1/2 - 1/2(n Omega(1));3. if s(n) = 2(Omega(n)), we amplify to hardness 1/2 - 1/2(Omega(root n)).Our results improve those of of O'Donnell, which amplify to 1/2 - 1/root n. O'Donnell also proved that no construction of a certain general form could amplify beyond 1/ 2 - 1/ n. We bypass this barrier by using both derandomization and nondeterminism in the construction of f'.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).
dc.language.isoen_US
dc.publisherSociety for Industrial and Applied Mathematics
dash.licenseLAA
dc.titleUsing Nondeterminism to Amplify Hardness
dc.typeJournal Article
dc.description.versionAccepted Manuscript
dc.relation.journalSIAM Journal on Computing
dash.depositing.authorVadhan, Salil P.::d28d73f959e703cf11ee3bc464495f24::600
dc.date.available2019-10-03T17:42:15Z
dash.workflow.comments1Science Serial ID 86373
dc.identifier.doi10.1137/S0097539705447281
dash.source.volume35;4
dash.source.page903-931


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record