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