# Equivalance of statement

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.

Thanks.

## 1 Answer

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.

• 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 – aceminer Mar 24 '17 at 3:27