Return to Question

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary assignments by just looking at some type of average. The easiest example I can think of is probably a binary function that is somewhat linear. Now in order to count the number of assignments resulting into 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.

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

Thanks a lot, Alberto

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

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary assignments by just looking at some type of average. The easiest example I can think of is probably a binary function that is somewhat linear. Now in order to count the number of assignments resulting into 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)$

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.

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

Thanks a lot, Alberto

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary assignments by just looking at some type of average. The easiest example I can think of is probably a binary function that is somewhat linear. Now in order to count the number of assignments resulting into 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.

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

Thanks a lot, Alberto

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary assignments by just looking at some type of average. The easiest example I can think of is probably a binary function that is somewhat linear. Now in order to count the number of assignments resulting into 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)$

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. I would really appreciate any pointers or references or just names for what I am actually looking for.

Thanks a lot, Alberto

Hey guys,

I have a slightly imprecise question. I would like say something about a whole set of binary assignments by just looking at some type of average. The easiest example I can think of is probably a binary function that is somewhat linear. Now in order to count the number of assignments resulting into 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)$

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.

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

Thanks a lot, Alberto