Question

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

Answer 1

(This should be a comment, but I don't have enough reputation to post a comment.) I have some clarifications regarding the question.

1. I guess I can think of each hash function as just a $\lbrace \pm 1 \rbrace^n$ vector $u$ with at most $k = n^\epsilon$ ones. Is this correct?
2. Also I don't understand the "above the expectation" condition. Why can't you just take two (arbitrary) vectors $u_1$ and $u_2$ with $k$ ones each, and at least one of them will have inner product at least equal to the expectation? Is it important that you strictly exceed the expectation? Do you want a constant fraction to be $\delta$ more than the expectation for some small $\delta > 0$?

@Guy: please feel free to use the latex features of this site; it makes reading remarkably easier.

Answer 2

Thanks for the answer - this was my first question, and I apologize for not knowing about the latex here.

About the comments in the previous post (Srivatsan):

1. This is correct - I'm trying to build an epsilon net for linear threshold functions, and this would be an important part of it. The "hash function" notation looks useful to me, since this reminds me of perfect hashing and similar concepts, where we are looking for some sort of "independence" or something similar between hash functions.

2. Since I'm trying to build a polynomial-size epsilon net, I need my family of vectors ("hash functions") to be very small in comparison with the family of all possible vectors, but still have a "good" inner product with $every$ other vector (at least for a constant factor of them). So I cannot take $u_1$ and $u_2$ as you ask and take their product, but I'm rather given an arbitrary vector $v\in\mathbb{R}^n$, and must find $u$ in my family which achieves a better inner product than the expectation (taken over the choice of any random vector with $k$ coordinates equal to 1).

Thanks, and hope this was a little clearer.

Guy