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



boolean functions and averaging / counting
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: [Finding minimal or canonical expressions for Boolean truth tables](https://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.)


