[chaoxu]

For cs people the more important would be property testing, since often we are interested in finding out if something holds with high probability without read everything. A common possibility is mapping a subset of set of vertices of a graph to a boolean. say, is the subset of vertices a independent set.

The simplest example would be testing how close f is to a linear function.

We consider f:{0,1}^n->{0,1}. f is linear if f(x+y)=f(x)+f(y), and there are different ways to measure almost linearity. Either the probability that randomly picking x and y, we have f(x+y)=f(x)+f(y), the other would be how far away the function is from a linear function in hamming distance.

Using the tools in analysis of boolean functions, we can show these two measures are basically the same.

http://www.contrib.andrew.cmu.edu/~ryanod/?p=279