Randomized algorithm for coloring with monochromatic copies Consider the complete graph $K_n$. Give a randomized algorithm for finding a coloring by two colors with at most $\binom{n}{4}2^{-5}$ monochromatic copies of $K_4$ that runs in expected time polynomial in $n$. Such a coloring exists by the probabilistic method. If we color each edge randomly, the expected number of monochromatic copies of $K_4$ is exactly $\binom{n}{4}2^{-5}$. Hence at least one coloring yields at least this many monochromatic copies. A natural algorithm is to randomly color the edges, and check whether the number of monochromatic edges is at least $\binom{n}{4}2^{-5}$. (This check can be done in $O(n^4)$, which is polynomial time.) If not, rerandomize all the colors of the edges. Keep doing this until we find a desired coloring. Now, is this algorithm polynomial time? We need to analyze the probability of success of each coloring. But that seems complicated.

Here's a non random algorithm to solve this. First, we clear the color of all the edges. Then, at each step, for each edge, suppose we color the edge white (similarly black). Then, compute the expected number of monochromatic copies of $K_4$ in the resulting graph. Pick an edge and color that minimize this expectation, and color the edge with that color. This is clearly polynomial in $n$ (maybe $O(n^6)$).

...now that we have a non randomized algorithm, we can always make it a randomized algorithm by, for eexample, instead of trying every edge and find the one that minimize the expectation, we can instead try random edges until we find one that makes the expectation still not greater than $\binom n4 2^{-5}$. This is still polynomial in average, but is this cheating?