Hi all,

As a part of a research I'm working on (involving derandomization of linear threshold functions), I'm trying to understand the following problem:

Is there a small (polynomial rather than exponential) family of hash functions, from [k] to [n] (k much smaller than n, say n^{epsilon}), which guarantee a "high inner product" with constant probability for every vector in R^n?

"high inner product" should be interpreted as following: The result of the hash function represents a vector in the binary hypercube, with 1 in every bucket which a coordinate of [k] is mapped into, and -1 elsewhere. Given a vector v in R^n, I would like at least a small constant factor of my hash functions to have an inner product which is above the expectation.

Is this possible? Does someone here have an idea for some pointers?

Thanks, Guy