3
$\begingroup$

I am trying to understand the sentence from a paper by Patrascu:

Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity

The context is a reduction between two variants of the 3-SUM problem:

  • In the usual variant, 3SUM, given an array $A$ we have to find 3 indices $i,j,k$ such that: $A[i]+A[j]=A[k]$.
  • In the other variant, Conv3SUM, we have to find 2 indices $i,j$ such that: $A[i]+A[j]=A[i+j]$.

Theoretically, we could reduce 3SUM to Conv3SUM if we had a linear hash function - a function $h$ such that: $h(x+y)=h(x)+h(y)$, and that maps all elements of $A$ to the range of indices $\{0,...,n-1\}$

The reduction is by sending every element of $A$ to an index determined by $h$, i.e. create an array $B$ such that for every $x\in A$: $B[h(x)]=x$

Then, if there is a solution to 3SUM on A, $x+y=z$, then on B we will have: $B[h(x)]+B[h(y)]=B[h(z)]$, and by the linearity of $h$ also $h(x)+h(y)=h(z)$, so this is a solution to Conv3SUM on B.

Conversely, every solution to Conv3SUM on B is trivially a solution to 3SUM on A, since every element of B is also an element of A.

Unfortunately, we do not have linear perfect hashing, so we have to use a family of almost-linear hash functions.

MY QUESTION IS: why do we have perfect almost-linear hash functions and not perfect linear hash functions? How does almost-linearity make it easier to find perfect hash functions?

$\endgroup$
2
  • $\begingroup$ It is trivial to find perfect linear hash functions. The hash function $h(x)=x$ satisfies all of your constraints. If you want one whose output is much shorter than the input $h(x)=x \bmod p$ is linear. What are the additional constraints on your hash function that make those not a valid solution? $\endgroup$ – D.W. Feb 16 '15 at 19:32
  • $\begingroup$ I think the problem is that the function $h(x)=x \mod p$ is not surjective (as you said in your previous answer). But, an almost-linear function is also not surjective. This is what I fail to understand. $\endgroup$ – Erel Segal-Halevi Feb 17 '15 at 13:33
1
$\begingroup$

I think there is a constraint that the domain of the hashing function must be {0...n-1}, where n means the number of elements to hash. Only defining in this way , the reduction from 3SUM to Conv3SUM works.

The is an almost-linearity function in wiki. And it is easy to figure out a counter example for the existence of perfect linear hashing function.

Consider the following questions:

Let A = {1,2,3,4}, B={0,1,2,3}

  1. how many triples (x,y,z) satisfy x+y=z, where x,y,z are in A and distinct
  2. what if x,y,z are in B

The answer of the first question is

  1. 1+1=2
  2. 1+2=3
  3. 1+3=4
  4. 2+2=4

But there are only two triples in the second question. You can find out a bijective function, satisfying that linearity property, mapping A onto B .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.