Questions tagged [hash-function]
The hash-function tag has no usage guidance.
17
questions with no upvoted or accepted answers
6
votes
0
answers
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
5
votes
0
answers
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
5
votes
0
answers
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
4
votes
0
answers
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 ...
- 41
4
votes
0
answers
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
3
votes
0
answers
122
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 778
3
votes
0
answers
68
views
one-way functions vs. secret-coin CRHFs
Is there any paper which can be used to show that there can be no relativizing construction of a secret-coin Collision-Resistant Hash Family from a one-way function and unlike this paper, does not ...
user6973
2
votes
0
answers
166
views
Locality Sensitive Hashing - meaning of a block
I'm reading one of the early LSH papers and I'm a little confused by the meaning of a "block". In particular, in the proof of theorem 1 in section 3.2 (p 522), what are the blocks being pointed to? ...
- 21
1
vote
0
answers
107
views
Sampling from a family of hash functions, not uniformly at random?
Many algorithms and data structures assume access to a family of hash functions satisfying some nice property (say, $k$-independence or $k$-universality). In these cases, we usually assume that we ...
- 2,121
1
vote
0
answers
184
views
Can a hash preimage be used to amplify BPP probabilities?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample a number $...
- 1,063
1
vote
0
answers
106
views
LSH Probabilistic guarantees
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:
$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \...
- 21
1
vote
0
answers
122
views
Why do k min-hashes, instead of one hash where we find the k minimum elements?
Traditionally if one wants to sketch streams for Jaccard similarity hashing, one finds the minimum element in each of $k$ permutation for comparison purposes, and then takes number_of_collisions / $k$ ...
- 729
1
vote
0
answers
89
views
Entropy criterion of efficiency for (comparison using hashing)
I understand that hash is effective iff the "domain" size is smaller than the size of the "general set" - set of all possible objects.
E.g., "domain" is the set of valid english phrases with length ...
- 11
0
votes
2
answers
33
views
Combining different length epsilon-ADU hash function families
For context, an $\epsilon$-almost delta universal ($\epsilon$-ADU) hash function family $\mathcal{H} = \{h : M \to D\}$ hashes inputs from $M$ to digests in $D$ such that
for any distinct $m, m' \in M$...
- 720
0
votes
0
answers
61
views
Reference Request : Accessible reference for Randomised algorithms and Hashing for non-Computer Scientists?
My goal is to understand well a paper like ApproxMC. It discusses the use of Hash functions for Propositional Model Counting. In my understanding what they call hash functions are just random XOR's ...
- 706
0
votes
0
answers
190
views
"Fair" hash functions
Motivation. When I use a hash function, I would like my pre-images (original values) to a given output (hash) to be evenly distributed as it could be that an uneven distribution could make guessing / ...
0
votes
0
answers
124
views
count number of i such that ( (a*i+b) mod p) mod k == l
How to determine the number of $i$'s as fast as possible such that
$$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$
where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$.
This ...
- 121