Healy, AlexanderVadhan, SalilViola, Emanuele2019-10-032006Healy, 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.0097-53971095-7111http://nrs.harvard.edu/urn-3:HUL.InstRepos:41467485We 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).en-USJournal Article2019-10-0310.1137/S0097539705447281