As mentioned earlier in Section 2 that distributional problems under flat distributions cannot be complete under (deterministic) p-time reductions if nondeterministic exponential time is strictly more powerful than deterministic exponential time [Gur91], and it cannot be complete, without any assumption, under one-one, p-length-preserving, and p-time computable reductions [WB95]. Note that the reductions constructed in the completeness proofs above are all one-one and p-length-preserving. Since instances under flat distributions have uniformly small weights on instance size, searching for frequent enough instances of the target problem of a reduction to uniformly dominate frequent instances of the source problem is crucial. Venkatesan and Levin [VL88] suggested to provide reductions with a good random source to help produce instances of the target problem with large enough probability. They showed that the distributional graph edge coloring problem is complete under a randomized reduction by allowing algorithms to toss coins to determine the next moves. Recall that the distribution of this problem is flat. The theory of randomized reductions was further studied by Blass and Gurevich [BG93][BG91].