What is an example of a weakly universal hash function that is not pairwise independent?
$begingroup$
A family of hash functions $H_w$ is said to be weakly universal if for all $x ne y$ :
$$P_{h in H_w}(h(x) = h(y)) leq 1/m$$
Here the function $h:U rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.
A family of hash functions $H_s$ is said to be strongly universal if for all $x ne y$ and $k, ell in [m]$:
$$P_{h in H_s}(h(x) = k land h(y) = ell) = 1/m^2$$
What is a concrete example of a hash function family which is weakly universal but not strongly universal?
hash hash-tables probabilistic-algorithms
asked Feb 14 at 16:33
AnushAnush
1407
$endgroup$
add a comment |
$begingroup$
A family of hash functions $H_w$ is said to be weakly universal if for all $x ne y$ :
$$P_{h in H_w}(h(x) = h(y)) leq 1/m$$
Here the function $h:U rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.
A family of hash functions $H_s$ is said to be strongly universal if for all $x ne y$ and $k, ell in [m]$:
$$P_{h in H_s}(h(x) = k land h(y) = ell) = 1/m^2$$
What is a concrete example of a hash function family which is weakly universal but not strongly universal?
hash hash-tables probabilistic-algorithms
asked Feb 14 at 16:33
AnushAnush
1407
$endgroup$
add a comment |
$begingroup$
A family of hash functions $H_w$ is said to be weakly universal if for all $x ne y$ :
$$P_{h in H_w}(h(x) = h(y)) leq 1/m$$
Here the function $h:U rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.
A family of hash functions $H_s$ is said to be strongly universal if for all $x ne y$ and $k, ell in [m]$:
$$P_{h in H_s}(h(x) = k land h(y) = ell) = 1/m^2$$
What is a concrete example of a hash function family which is weakly universal but not strongly universal?
hash hash-tables probabilistic-algorithms
asked Feb 14 at 16:33
AnushAnush
1407
$endgroup$
A family of hash functions $H_w$ is said to be weakly universal if for all $x ne y$ :
$$P_{h in H_w}(h(x) = h(y)) leq 1/m$$
Here the function $h:U rightarrow [m]$ is chosen uniformly from the family $H$ and we assume $|U| > m$.
A family of hash functions $H_s$ is said to be strongly universal if for all $x ne y$ and $k, ell in [m]$:
$$P_{h in H_s}(h(x) = k land h(y) = ell) = 1/m^2$$
What is a concrete example of a hash function family which is weakly universal but not strongly universal?
hash hash-tables probabilistic-algorithms
hash hash-tables probabilistic-algorithms
asked Feb 14 at 16:33
AnushAnush
1407
asked Feb 14 at 16:33
AnushAnush
1407
edited Feb 14 at 17:07
Anush
asked Feb 14 at 16:33
AnushAnush
1407
asked Feb 14 at 16:33
AnushAnush
1407
asked Feb 14 at 16:33
AnushAnush
1407
1407
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i in [m]$, given by
$$
h_i(x) = begin{cases}
x & text{if } x neq m+1, \
i & text{if } x = m+1.
end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
$endgroup$
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
|
show 3 more comments
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104361%2fwhat-is-an-example-of-a-weakly-universal-hash-function-that-is-not-pairwise-inde%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i in [m]$, given by
$$
h_i(x) = begin{cases}
x & text{if } x neq m+1, \
i & text{if } x = m+1.
end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
$endgroup$
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
|
show 3 more comments
$begingroup$
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i in [m]$, given by
$$
h_i(x) = begin{cases}
x & text{if } x neq m+1, \
i & text{if } x = m+1.
end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
$endgroup$
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
|
show 3 more comments
$begingroup$
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i in [m]$, given by
$$
h_i(x) = begin{cases}
x & text{if } x neq m+1, \
i & text{if } x = m+1.
end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
$endgroup$
Let $U = [m]$, and let $h$ be the identity function.
If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i in [m]$, given by
$$
h_i(x) = begin{cases}
x & text{if } x neq m+1, \
i & text{if } x = m+1.
end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
edited Feb 14 at 17:19
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
answered Feb 14 at 16:59
Yuval FilmusYuval Filmus
193k14181345
193k14181345
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
|
show 3 more comments
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
$begingroup$
Oh sorry. I meant $|U|$ to be larger than $m$? Let me fix that.
$endgroup$
– Anush
Feb 14 at 17:07
2
2
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
Is there anything else you forgot about the question? I don't like continuously changing my answer to fit an ever-changing question.
$endgroup$
– Yuval Filmus
Feb 14 at 17:12
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
$begingroup$
No I don’t think so. Thank you for your very nice answer to the first version.
$endgroup$
– Anush
Feb 14 at 17:13
1
1
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
$begingroup$
Well, it makes a nice exercise.
$endgroup$
– Yuval Filmus
Feb 14 at 17:24
1
1
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
$begingroup$
I don’t see any lookup tables in your question. Perhaps you need to spend more time formulating your question. When you have a concrete follow-up question, you can ask it separately.
$endgroup$
– Yuval Filmus
Feb 14 at 18:58
|
show 3 more comments
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f104361%2fwhat-is-an-example-of-a-weakly-universal-hash-function-that-is-not-pairwise-inde%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
