[amathstudent]

I was wondering: I find this topic interesting from a conceptual point of view, but I'm reluctant to learn more about it without having some concrete useful application as motivation. Can anyone give an example like that?

[chaoxu]

As far as I know, the applications are for theoretical problems and has no application in everyday work.

[toddkaufmann]

I bet someday a use for 1's and 0's are found (not necessarily in that order).

[amathstudent]

That's fine, I like theoretical problems too.

[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