Four Derandomization Problems

Polymath4 is devoted to a question about derandomization: To find a deterministic polynomial time algorithm for finding a k-digit prime.  So I (belatedly) devote this post to derandomization and, in particular, the following four problems.

1) Find a deterministic algorithm for primality

2) Find a combinatorial characterization (and a deterministic algorithm) for generically 3-rigid graphs

3) Find an explicit construction for Ramsey graphs

4) Find a deterministic method for polling

(Remark: I was very slow in writing this post, and I had to give up elaborating the details on some very nice topics in order to finish it.)


Continue reading