<p>Consider a <em>boolean</em> function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The question is to decide whether there are $\vec{x}$ and $\vec{x}'$ such that </p>

<p>$g(\vec{x})\neq g(\vec{x}')$. </p>

<p>The computation of $g$ is $\sharp P$-hard, However, I am still seeking practically efficient (approximate, randomized) algorithms. Possibly one does not need to compute $g$ directly?</p>

<p>One might view the problem from a couple of different perspectives: it is a polynomial identity testing problem, but here, it is over $F_2$ which the  Schwartz-Zippel Algorithm might not work (I am not sure although); or it is a problem of analysis of boolean functions, but this  is a bit vague, and I am not clear whether powerful techniques (e.g., Fourier analysis) are applicable here. Any hints are highly appreciated. </p>

CC BY-SA 3.0
2016-06-03T12:53:36.787Z
How is f given? If it is given as a table then the problem is in P. If it is a fixed polynomial time computable function then there are f for which this is #P hard.
Kaveh
CC BY-SA 3.0
2016-06-03T13:13:00.283Z
Does $\sum$ stand for disjunction, xor, or something else?
Emil Jeřábek
CC BY-SA 3.0
2016-06-03T13:18:52.593Z
@Kaveh, $f$ is given as a branching program, not a truth table. And you are right, this is not in NP (I was thinking of $g(x)\neq g(x')$ and clearly this is not enough).
maomao
CC BY-SA 3.0
2016-06-03T13:23:18.720Z
@EmilJeřábek, $\sum$ is just to take the sum. Note that here $f$ is 0,1-valued, $g$ basically counts the "probability" of $f$ being 1.
maomao
CC BY-SA 3.0
2016-06-03T13:29:43.767Z
I don't understand what do you mean by "just take the sum". Since these are Boolean function, presumably you take some + operation {0,1}×{0,1}->{0,1}. Which one? Be specific.
Emil Jeřábek
CC BY-SA 3.0
2016-06-03T13:39:51.123Z
@EmilJeřábek, please notice that $f$ is a boolean function, while $g$ is not, although it is still over boolean variables $\vec{x}$.
maomao
CC BY-SA 3.0
2016-06-03T13:43:01.347Z
Are you trying to say that you upgrade $f$ to an integer-valued function and perform the sum in the integers, or something? Can you just state it clearly?
Emil Jeřábek
CC BY-SA 3.0
2016-06-04T16:49:49.557Z
@Kaveh: How are you getting #P-hardness for this problem under arbitrary $f$? Just knowing if there are $x,x'$ for which $g(x)\ne g(x')$ doesn't seem to me to be a powerful enough mechanism to count. I know NP-hardness follows from considering $f(x,y) = x\cdot \varphi(y)$.
Andrew Morgan
CC BY-SA 3.0
2016-06-04T17:00:24.157Z
If $f$ satisfies the promise that, either $g(x) = g(x')$ for all $x,x'$, or else there are values of $x,x'$ such that $g(x') / g(x) \ge 1/\text{poly}$, then you can use that "approximate counting is in $\mathrm{BPP}^\mathrm{NP}$" to get an $\mathrm{MA}^\mathrm{NP}$ algorithm: Merlin sends $x,x'$, and then Arthur approximately counts $g(x)$ and $g(x')$ to within enough accuracy to separate them.
Andrew Morgan
<cc.complexity-theory><boolean-functions><polynomials>
Identity testing of margins of boolean functions
maomao
# Identity testing of margins of boolean functions

(Asked by: username_0 on 2016-06-03)

Consider a *boolean* function $f(\vec{x},\vec{y})$, we define an (integer-valued) function $g(\vec{x})=\sum\_{\vec{y}}f(\vec{x},\vec{y})$, i.e., $g$ can be considered as a (sort of) margin of $f$. The question is to decide whether there are $\vec{x}$ and $\vec{x}'$ such that

$g(\vec{x})\neq g(\vec{x}')$.

The computation of $g$ is $\sharp P$-hard, However, I am still seeking practically efficient (approximate, randomized) algorithms. Possibly one does not need to compute $g$ directly?

One might view the problem from a couple of different perspectives: it is a polynomial identity testing problem, but here, it is over $F\_2$ which the Schwartz-Zippel Algorithm might not work (I am not sure although); or it is a problem of analysis of boolean functions, but this is a bit vague, and I am not clear whether powerful techniques (e.g., Fourier analysis) are applicable here. Any hints are highly appreciated.

**Tags:** cc.complexity-theory, boolean-functions, polynomials
> **Comments:**
> **username_1**: How is f given? If it is given as a table then the problem is in P. If it is a fixed polynomial time computable function then there are f for which this is #P hard.  
> **username_2**: Does $\sum$ stand for disjunction, xor, or something else?  
> **username_0**: @Kaveh, $f$ is given as a branching program, not a truth table. And you are right, this is not in NP (I was thinking of $g(x)\neq g(x')$ and clearly this is not enough).  
> **username_0**: @EmilJeřábek, $\sum$ is just to take the sum. Note that here $f$ is 0,1-valued, $g$ basically counts the "probability" of $f$ being 1.  
> **username_2**: I don't understand what do you mean by "just take the sum". Since these are Boolean function, presumably you take some + operation {0,1}×{0,1}->{0,1}. Which one? Be specific.  
> **username_0**: @EmilJeřábek, please notice that $f$ is a boolean function, while $g$ is not, although it is still over boolean variables $\vec{x}$.  
> **username_2**: Are you trying to say that you upgrade $f$ to an integer-valued function and perform the sum in the integers, or something? Can you just state it clearly?  
> **username_3**: @Kaveh: How are you getting #P-hardness for this problem under arbitrary $f$? Just knowing if there are $x,x'$ for which $g(x)\ne g(x')$ doesn't seem to me to be a powerful enough mechanism to count. I know NP-hardness follows from considering $f(x,y) = x\cdot \varphi(y)$.  
> **username_3**: If $f$ satisfies the promise that, either $g(x) = g(x')$ for all $x,x'$, or else there are values of $x,x'$ such that $g(x') / g(x) \ge 1/\text{poly}$, then you can use that "approximate counting is in $\mathrm{BPP}^\mathrm{NP}$" to get an $\mathrm{MA}^\mathrm{NP}$ algorithm: Merlin sends $x,x'$, and then Arthur approximately counts $g(x)$ and $g(x')$ to within enough accuracy to separate them.  

---

## 0 answers

