Difference between revisions of "Open Problems:58"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Added example of why linearity is useful.)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Signatures for Set Equality
 
 
|source=dortmund12
 
|source=dortmund12
 
|who=Rasmus Pagh
 
|who=Rasmus Pagh
Line 8: Line 7:
 
# $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.
 
# $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:''' 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. Linearity would imply, for example, that if $S_1 \subseteq S_2$ we can compute $h(S_2\backslash S_1)$ in constant time, as the difference of $h(S_2)$ and $h(S_1)$.

Latest revision as of 05:51, 18 April 2013

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:

  1. $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.
  2. $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. Linearity would imply, for example, that if $S_1 \subseteq S_2$ we can compute $h(S_2\backslash S_1)$ in constant time, as the difference of $h(S_2)$ and $h(S_1)$.