4 ms·
Analysis of Boolean Functions
- amathstudent 12y agoI 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 12y agoAs far as I know, the applications are for theoretical problems and has no application in everyday work.
- amathstudent 12y agoThat's fine, I like theoretical problems too.
- chaoxu 12y agoFor 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 http://www.contrib.andrew.cmu.edu/~ryanod/?p=279
- toddkaufmann 12y agoI bet someday a use for 1's and 0's are found (not necessarily in that order).
- deleted 12y ago[deleted]
- coin 12y agoInternal 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
- deleted 12y ago[deleted]