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