6
$\begingroup$

As part of a research project on derandomization of linear threshold functions I am working on, I am trying to understand the following problem:

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

The term "high inner product" should be interpreted as follows: 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 \mathbb 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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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 δ more than the expectation for some small δ>0? $\endgroup$
    – Srivatsan Narayanan
    Commented Jul 18, 2011 at 13:16
  • $\begingroup$ 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, (cont.) $\endgroup$
    – Guy Adini
    Commented Jul 19, 2011 at 15:00
  • $\begingroup$ 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 u1 and u2 as you ask and take their product, but I'm rather given an arbitrary vector v∈ℝ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. $\endgroup$
    – Guy Adini
    Commented Jul 19, 2011 at 15:00
  • 2
    $\begingroup$ I think this question needs more formal definitions. What I would call a hash function is rather a map $\{0,1\}^k \to \{0,1\}^n$ with $k \gg n$ (an in principle, the argument should in fact be allowed to have variable length). $\endgroup$
    – Benoît Kloeckner
    Commented Dec 16, 2017 at 16:36
  • $\begingroup$ You're thinking of cryptographic hash functions, there are other types, with the relationship between $k$ and $n$ reversed. $\endgroup$
    – kodlu
    Commented Feb 14, 2018 at 20:13

0

Reset to default

You must log in to answer this question.