> There are problems for which deterministic exact sublinear time algorithms are known.
I can imagine silly examples (like "find the minimum element in this list under the assumption that no more than O(sqrt(n)) elements exceed the minimum"...), but what's an interesting example of this?
I can imagine silly examples (like "find the minimum element in this list under the assumption that no more than O(sqrt(n)) elements exceed the minimum"...), but what's an interesting example of this?