Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

[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).

share|cite|improve this question
up vote 2 down vote accepted

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.)

share|cite|improve this answer
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. :-) – Niel de Beaudrap Jan 11 '12 at 21:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.