Progress in randomized algorithms

The following article was written in 1984 as a non-technical "column" in a research journal:

"The NP-Completeness Column: An Ongoing Guide", David S. Johnson

Don't be intimidated by the title, or if you don't understand every word. I want you to read the first two sections of this article (up to page 6), which is mostly a summary of a number of problems where the randomized algorithm is faster than the best known deterministic one.

THe problems that are mentioned include: testing if a number is prime, finding the closest pair of points in a square region, determining whether two sets of polynomials have the same product, factoring polynomials, and determining whether two graphs are equivalent ("graph isomorphism").

After reading the first two sections, pick one of the problems that is mentioned. Then do three things:

1. Briefly re-state what the problem is.
2. Summarize what the article says about the fastest randomized and deterministic algorithms for that problem in 1984.
3. Do some research to determine what progress, if any, has been made since
   1984. Have faster deterministic or randomized algorithms been developed? Are there faster algorithms for some special cases of the original problem? Are there new lower bounds or impossibility results for the problem? Wikipedia and Google are your friends here.
   Start by looking up the problem, and maybe look up the references as well. Note that the "introduction" paragraph of most research articles is supposed to be easy to read and summarize the contribution of that article as well as the prior history of the problem. Ask Dr. Roche if you need any help with this.