Hardness amplification for errorless heuristics

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol ⊥, which means “I don’t know. ” A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ> 0, runs in time polynomial in the instance size and 1/δ and answers ⊥ only on a δ fraction of instances. We study the question from the standpoint of hardness amplification and show that • If every problem in (NP,U) has errorless heuristic circuits that output the correct answer on n−2/9+o(1)-fraction of inputs, then (NP,U) has non-uniform errorless heuristic schemes. • If every problem in (NP,U) has randomized errorless heuristic algorithms that output the correct answer on (logn)−1/10+o(1)-fraction of inputs, then (NP,U) has randomized errorless heuristic schemes. In both cases, the low-end amplification is achieved by analyzing a new sensitivity property of monotone boolean functions in NP. In the non-uniform setting we use a ”holographic function” introduced by Benjamini, Schramm, and Wilson (STOC 2005). For the uniform setting we introduce a new function that can be viewed as an efficient version of Talagrand’s ”random DNF”.