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.

  • $\begingroup$ 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. $\endgroup$ – Kaveh Jun 3 '16 at 12:53
  • $\begingroup$ Does $\sum$ stand for disjunction, xor, or something else? $\endgroup$ – Emil Jeřábek Jun 3 '16 at 13:13
  • $\begingroup$ @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). $\endgroup$ – maomao Jun 3 '16 at 13:18
  • $\begingroup$ @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. $\endgroup$ – maomao Jun 3 '16 at 13:23
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Jun 3 '16 at 13:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.