Hacker News new | ask | show | jobs
by chaoxu 4325 days ago
As far as I know, the applications are for theoretical problems and has no application in everyday work.
2 comments

I bet someday a use for 1's and 0's are found (not necessarily in that order).
That's fine, I like theoretical problems too.
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