dc.contributor.author | Healy, Alexander | |
dc.contributor.author | Vadhan, Salil | |
dc.contributor.author | Viola, Emanuele | |
dc.date.accessioned | 2019-10-03T17:42:15Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Healy, 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.issn | 0097-5397 | |
dc.identifier.issn | 1095-7111 | |
dc.identifier.uri | http://nrs.harvard.edu/urn-3:HUL.InstRepos:41467485 | * |
dc.description.abstract | We 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.iso | en_US | |
dc.publisher | Society for Industrial and Applied Mathematics | |
dash.license | LAA | |
dc.title | Using Nondeterminism to Amplify Hardness | |
dc.type | Journal Article | |
dc.description.version | Accepted Manuscript | |
dc.relation.journal | SIAM Journal on Computing | |
dash.depositing.author | Vadhan, Salil P.::d28d73f959e703cf11ee3bc464495f24::600 | |
dc.date.available | 2019-10-03T17:42:15Z | |
dash.workflow.comments | 1Science Serial ID 86373 | |
dc.identifier.doi | 10.1137/S0097539705447281 | |
dash.source.volume | 35;4 | |
dash.source.page | 903-931 | |