Difference between revisions of "Open Problems:58"
(Created page with "{{Header |title=Signatures for set equality |source=dortmund12 |who=Rasmus Pagh }} Given $S\subseteq\{1,..n\}$, we would like to construct a fingerprint so that later, given f...") |
|||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |title=Signatures for | + | |title=Signatures for Set Equality |
|source=dortmund12 | |source=dortmund12 | ||
|who=Rasmus Pagh | |who=Rasmus Pagh | ||
}} | }} | ||
| − | Given $S\subseteq\{1,..n\}$, we would like to construct a fingerprint so that later, given fingerprints of two sets, we can check the equality of the two sets. | + | Given $S\subseteq\{1,..n\}$, we would like to construct a fingerprint so that later, given fingerprints of two sets, we can check the equality of the two sets. There are (at least) two possible solutions to the problem: |
| + | # $h(S)=\left(\sum_{i\in S} x^i\right)\bmod p$ for random $x\in \Z_p$. Update time would be roughly $\log p=\Omega(\log n)$. One would like to obtain a better update time. | ||
| + | # $h(S)=\left(\prod_{i\in S} (x-i)\right) \bmod p$, and random $x$. Insertion can be done in constant time. But the fingerprint is not linear. | ||
| − | + | '''Question:''' Can we construct a fingerprint that achieves constant update time and is linear, while using $O(\log n)$ random bits? Ideally updates would include insertions and deletions. | |
| − | |||
| − | |||
| − | |||
| − | '''Question''' | ||
Revision as of 05:11, 12 December 2012
| Suggested by | Rasmus Pagh |
|---|---|
| Source | Dortmund 2012 |
| Short link | https://sublinear.info/58 |
Given $S\subseteq\{1,..n\}$, we would like to construct a fingerprint so that later, given fingerprints of two sets, we can check the equality of the two sets. There are (at least) two possible solutions to the problem:
- $h(S)=\left(\sum_{i\in S} x^i\right)\bmod p$ for random $x\in \Z_p$. Update time would be roughly $\log p=\Omega(\log n)$. One would like to obtain a better update time.
- $h(S)=\left(\prod_{i\in S} (x-i)\right) \bmod p$, and random $x$. Insertion can be done in constant time. But the fingerprint is not linear.
Question: Can we construct a fingerprint that achieves constant update time and is linear, while using $O(\log n)$ random bits? Ideally updates would include insertions and deletions.
