Consider the following problem:
Input: lists $X,Y$ of integers
Goal: determine whether there exists an integer $x$ that is in both lists.
Suppose both lists $X,Y$ are of size $n$. Is there a deterministic, linear-time algorithm for this problem? In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?
Unfortunately, you cannot assume that the list elements are all small.
I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable. The expected running time will be $O(n)$. However, I can't see how to find a deterministic algorithm with $O(n)$ running time. If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time. The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time. Can we achieve linear running time?
Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.
If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation. I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.