Here’s an algorithm that I’ve heard is either really hard to derandomize, or has been proven impossible to derandomize. (I couldn’t find a reference for the latter claim.) Find an arbitrary prime between two large numbers, like 10^500 − 10^501. The problem with searching sequentially is that there are arbitrarily long stretches of composites among the naturals, and if you start somewhere in one of those you’ll end up spending a lot more time before you get to the end of the stretch.
See the Polymath project on that subject. The conjecture is that it is possible to derandomize, but it hasn’t been proven either way. Note that finding an algorithm isn’t the hard part: if a deterministic algorithm exists, then the universal dovetail algorithm also works.
Here’s an algorithm that I’ve heard is either really hard to derandomize, or has been proven impossible to derandomize. (I couldn’t find a reference for the latter claim.) Find an arbitrary prime between two large numbers, like 10^500 − 10^501. The problem with searching sequentially is that there are arbitrarily long stretches of composites among the naturals, and if you start somewhere in one of those you’ll end up spending a lot more time before you get to the end of the stretch.
See the Polymath project on that subject. The conjecture is that it is possible to derandomize, but it hasn’t been proven either way. Note that finding an algorithm isn’t the hard part: if a deterministic algorithm exists, then the universal dovetail algorithm also works.