# Questions tagged [hash-function]

The tag has no usage guidance.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
133 views

### Consistent Sampling a Random Walk

Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid. I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
• 958
483 views

### Tuning Parameters of Locality Sensitive Hashing

We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ ...
• 639
253 views

### Ergodic Theory and Hash Functions

I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, ...
• 193
117 views

### How many bits are required to sample an almost pairwise independent hash function?

A family of functions $\mathcal{H} = \{ h\colon \{0,1\}^n \to \{0,1\}^m \}$ is said to be $\varepsilon$-almost pairwise independent if, for every distinct $x_1,x_2 \in \{0,1\}^n$ and (not necessarily ...
150 views

### What degree of hash function independence is needed for Bloom filters?

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
• 2,121
122 views

• 1,063
1 vote