Random Self-reducibility - Definition

Definition

If a function f evaluating any instance x can be reduced in polynomial time to the evaluation of f on one or more random instances y_i, then it is self-reducible (this is also known as a non-adaptive uniform self-reduction). In a random self-reduction, an arbitrary worst-case instance x in the domain of f is mapped to a random set of instances y₁, ..., y_k. This is done so that f(x) can be computed in polynomial time, given the coin-toss sequence from the mapping, x, and f(y₁), ..., f(y_k). Therefore, taking the average with respect to the induced distribution on y_i, the average-case complexity of f is the same (within polynomial factors) as the worst-case randomized complexity of f.

One special case of note is when each random instance y_i is distributed uniformly over the entire set of elements in the domain of f that have a length of |x|. In this case f is as hard on average as it is in the worst case. This approach contains two key restrictions. First the generation of y₁, ..., y_k is performed non-adaptively. This means that y₂ is picked before f(y₁) is known. Second, it is not necessary that the points y₁, ..., y_k be uniformly distributed.