boolean functions and averaging / counting - MathOverflow

boolean functions and averaging / counting

2010-09-17T00:18:28Z

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest example I can think of is probably a binary function $f: \{0,1\}^n \rightarrow \{0,1\}$ that is linear with $f(0) = 0$. Now in order to count the number of assignments resulting in $1$ I can do the following:

$1/2^n * \sum_{x \in \{0,1\}^n} f(x) = f(1/2^n * \sum_{x \in \{0,1\}^n} x) = f(1/2 e)$

where $e = (1,\dots, 1)$ is the all-one vector and thus $f(1/2 e) * 2^n$ gives me the answer i am looking for.

I vaguely recall that I have seen something like this beforehand and I guess that there is something like a whole theory about this type of combinatorial argument out there. It is also somehow about inferring the structure of the boolean function by evaluating it at non-boolean inputs. For example, I think that this is part of the idea of the algebraization as a barrier to showing P != NP where one of the oracles get enhanced power by not only being able to evaluate a certain function at 0/1 assignments but also any other point contained in $[0,1]^n$.

I would really appreciate any pointers or references or just names for what I am actually looking for.

Thanks a lot, Alberto

Answer by Gerhard Paseman for boolean functions and averaging / counting

2010-09-17T20:51:38Z

One view of this is integration. If the curve (function) you have is sufficiently well understood, you can estimate the area under it by various approximation rules using a few points, e.g. Simpson's Rule. Thus you can generalize your linear example.

The other ways below involve obtaining the average through evaluating the function at some of the points in {0,1}^n . They don't speak to how to use this to infer properties of the function.

If your function is monotonic increasing, then in principle you can find the set of points which are least and sent to one under the function, and then use some form of inclusion-exclusion to get the count, or perhaps something simpler.

If your function domain can be nicely partitioned so that the result is a disjoint union of monotonic functions, then you have a divide-and-conquer strategy to implement.

If your function looks like XOR of several variables in some places, those places contribute a weight 1/2 to the average, and you might be able to handle the other places by something similar to the above.

The quickest way to estimate the average is by random sampling. The average of the function is likely to be close to the average of a random sample.

Gerhard "Ask Me About System Design" Paseman, 2010.09.17

Answer by Nick S for boolean functions and averaging / counting

2010-09-17T20:54:21Z

For the finite case I don't know anything which helps, but if your space is infinite you are looking for an Ergodic Theorem (or some type of mean/amenability if you are not in the case of a Dynamical System).

Hpe this helps

Answer by Darsh Ranjan for boolean functions and averaging / counting

2010-09-18T03:58:43Z

There's a canonical way to extend a boolean function to the unit n-cube: you replace the boolean arguments by real numbers that are the probabilities of independent events, and the new output is the probability of the compound event defined by the original boolean function. For example, take the boolean function $(a,b,c)\mapsto (a\wedge b) \vee c$. If $a$, $b$, and $c$ are independent events with respective probabilities $p$, $q$, and $r$, then you can check that the probability of the event $(a\wedge b) \vee c$ is $pq +r -pqr$. I wrote a somewhat long post about this here: http://mathoverflow.net/questions/4930/finding-minimal-or-canonical-expressions-for-boolean-truth-tables/4951#4951

I bring this up because if $f$ is an n-ary boolean function and $f^*$ is the probability version, then $f^*(1/2,...,1/2)$ is precisely the average value of $f$ over all possible boolean inputs. (That's obvious: if you flip a fair coin to determine the truth value for each of the n arguments of $f$, then by definition, $f^*(1/2,...,1/2)$ is the probability of $f$ evaluating to "true," but that probability is also clearly the average value of $f$ in this case.) That seems to be what you're looking for. (Unfortunately, computing $f^*$ for any reasonably complicated function $f$ is pretty much intractable: indeed, there is no polynomial-time algorithm unless P = #P, by the simple fact stated above.)