1
$\begingroup$

[Edited. I've revised to problem to focus on the special case of the integers modulo 2.]

You are given a function f from binary strings x ∈ {0,1}n to the integers, or (without loss of generality) just to {0,1}. You are promised only that f is not entirely even numbers.

Question. With only poly(n) random bits, how do you describe a subset S ⊂ {0,1}n so that, with probability at least 1/poly(n), the sum (modulo p) of f(x) over all x ∈ S is odd?

I'm interested in efficient algorithms; for instance, searching for a single x ∈ {0,1}n for which f(x) is odd, by evaluating most of the values of x, is not allowed (as this takes exponential time in the worst case).

1 Answers 1

2

Notwithstanding my naive skepticism expressed in my comment, it turns out that this is possible: the proof of the Valiant-Vazirani theorem gives such an $S$.

  • As a preliminary step, guess the size of $\{ x \colon f(x) \text{ is odd} \}$ up to a factor of 2: i.e., guess an $r$ such that the size of that set is in the window $[2^{r-1}, 2^r)$. This guess is correct with probability $1/(n+1)$.

  • Pick $S$ to be a random subcube of codimension around $r$. (The codimension should be $r \pm$ an absolute constant. I do not know the details off the top of my head; I will update my answer later to make this precise). Then conditioned on our first guess being right, with a constant probability, it can be shown that there is exactly one $x \in S$ such that $f(x)$ is odd.

Thus $\sum \limits_{x \in S} f(x)$ is odd with probability $\Omega (\frac{1}{n})$. Done! (The description of $S$ takes $O(n)$ random bits.)

  • 1
    In retrospect, this cuts right to the heart of the problem: the sum of the integer sequence is effectively #SAT in disguise, and I'm effectively asking how to reduce the number of satisfying solutions to an odd number, e.g. a unique satisfying solution. The same principle applies for any finite field. I'll look over your answer after I've rested, and likely accept it then. :-)2012-01-11