Open Problems:58 - Revision history

Pagh: Added example of why linearity is useful.

2013-04-18T05:51:41Z

Added example of why linearity is useful.

Krzysztof Onak: updated header

2013-03-07T02:00:11Z

updated header

Krzysztof Onak at 05:11, 12 December 2012

2012-12-12T05:11:05Z

Andoni: 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..."

2012-12-12T02:10:06Z

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..."

New page

{{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 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)=\sum_{i\in S} x^i\mod 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)=\prod_{i\in S} (x-i) \mod 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.

← Older revision		Revision as of 05:51, 18 April 2013
Line 7:		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)$.

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Rasmus Pagh

@@ Line 1: / Line 1: @@
 {{Header
-|title=Signatures for set equality
+|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 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:
-There are (at least) two possible solutions to the problem:
+'''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.