I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika

Inside specifically had this statement.

Picking a random hyperplane amounts to choosing a normally
distributed random variable for each dimension. Thus
even representing a hash function in this family could require
a large number of random bits. However, for n vectors, the
hash functions can be chosen by picking O(log^2 n) random
bits, i.e. we can restrict the random hyperplanes to be in
a family of size 2^O(log^2 n)

I think it didnt make sense as what it means is that for each n vector, the dimensions would be log^2 n. However, the equivalent statement is that the hyperplanes can be in a family of size 2^O(log^2 n)

It doesnt seem to make any sense to me. Can someone explain to me why is this statement equals.



If you are picking $O(\log^2 n)$ bits, then the number of values that can be represented by those bits is $2^{O(\log^2 n))}$.

That is, $m$ bits can represent $2^m$ values.

  • $\begingroup$ So each vector can be represented as O(log^2 n) bits? If i have 4 vectors, it can be represented by log^2 (4) = 1, It can be represented by 1 bit? It seems a but funny that this is the case $\endgroup$ – aceminer Mar 24 '17 at 3:27

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.