Here is a post on derandomization. It includes material on the problem of finding a deterministic algorithm for finding primes. It also has a section on the construction of Ramsey graphs. There has recently been an improvement in this area although there is still a gap between constructed graphs and the random graphs.
http://gilkalai.wordpress.com/2009/12/06/four-derandomization-problems/#more-4446
