I think that this article shows a very interesting application of a technique known as “derandomization”. Usually, derandomization is when you take a randomized algorithm and remove all sources of randomness. In this application, we see it only partially derandomized, to great effect: copysets improve reliability by reducing overall randomness, but still leverage randomness to approximate the solution to an NP-complete problem.
I wonder if other algorithms would benefit from partial derandomization?
Comments
I think that this article shows a very interesting application of a technique known as “derandomization”. Usually, derandomization is when you take a randomized algorithm and remove all sources of randomness. In this application, we see it only partially derandomized, to great effect: copysets improve reliability by reducing overall randomness, but still leverage randomness to approximate the solution to an NP-complete problem.
I wonder if other algorithms would benefit from partial derandomization?