Analysis of Boolean Functions

contrib.andrew.cmu.edu

32 points·luu··6 comments

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?

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

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

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

Internal Server Error

The server encountered an internal error or misconfiguration and was unable to complete your request.

Please contact the server administrator, webmaster@club.cc.cmu.edu and inform them of the time the error occurred, and anything you might have done that may have caused the error.

More information about this error may be available in the server error log.

Apache/2.2.16 (Debian) Server at www.contrib.andrew.cmu.edu Port 80

Reply on news.ycombinator.com