Ask HN: Using Sublinear Time Algorithms?

Sublinear time algos are ones that do not look at all their input data (perhaps because it is too big, too expensive, etc) yet, try to provide high probability answers about it, often in the form of "property tests": ex: is this massive list sorted? One log(n) algo for this property is to repeatedly pick an element at random then look for it with binary search. If the list is sorted then you should find it every time (ok, assuming unique elems). The more times you repeat the test, the higher the probability that the list is sorted.

Are you using these in your work and can you say a few words about them? Any good references you can share? As an example, Ronitt Rubinfeld has given an engaging recent talk (yt). Her refs:

https://people.csail.mit.edu/ronitt/sublinear.html