Sublinear Time Algorithms

I am reading "Approximating the minimum spanning tree weight in sublinear time" by Chazelle, Robinfeld, and Trevisan. So far, we try to approximate problems NP. In this paper, I come to know it's very interesting to approximate polynomial time algorithms as data sets are really BIG nowadays. This raises a lot of open problems. Here is a useful page of Ronitt Rubinfeld for a starting point in this area.