# Finding a subsequence (of a very long sequence) which does not sum to an even number

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

-

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