Open Problems:47 - Revision history

Krzysztof Onak at 04:29, 28 April 2017

2017-04-28T04:29:51Z

Sassadi at 15:45, 20 April 2017

2017-04-20T15:45:39Z

Krzysztof Onak: updated header

2013-03-07T01:55:41Z

updated header

Krzysztof Onak: Created page with "{{Header |title=Annotated Streaming |source=bertinoro11 |who=Graham Cormode }} In the annotated stream model {{cite|ChakrabartiCM-09}}, a stream is augmented with ‘anno..."

2012-11-17T04:20:39Z

Created page with "{{Header |title=Annotated Streaming |source=bertinoro11 |who=Graham Cormode }} In the annotated stream model {{cite|ChakrabartiCM-09}}, a stream is augmented with ‘anno..."

New page

{{Header
|title=Annotated Streaming
|source=bertinoro11
|who=Graham Cormode
}}
In the annotated stream model {{cite|ChakrabartiCM-09}}, a stream is
augmented with ‘annotation’, which takes the form of a proof of a property of the stream.
In its simplest form, the annotation may just be a reordering of the stream to make it
easy to compute a function of interest. The key parameters in this model are $H$, the size
of the annotation, and $V$, the space needed by the streaming party to
view the stream and verify the proof. The annotation proposed should be such that an
honest annotation will always be accepted, while a mistaken annotation will be detected
and rejected with high probability.

We consider the problem of counting the number of triangles
in a graph described by a stream of edges (where each edge is promised to occur at most
once). Partial results from the above reference are that $H = O(n^2)$ and $V =
\tilde{O}(1)$ is possible, as is $H = O(n^{3/2}), V= O(n^{3/2})$.

'''Question:''' Can one achieve $H = V = \tilde{O}(n)$?

← Older revision		Revision as of 04:29, 28 April 2017
Line 21:		Line 21:
	== Update ==		== Update ==

−	This question was answered affirmatively by {{cite\|Thaler-16}}.	+	This question was answered affirmatively by Thaler {{cite\|Thaler-16}}.

← Older revision		Revision as of 15:45, 20 April 2017
Line 18:		Line 18:

	'''Question:''' Can one achieve $H = V = \tilde{O}(n)$?		'''Question:''' Can one achieve $H = V = \tilde{O}(n)$?
		+
		+	== Update ==
		+
		+	This question was answered affirmatively by {{cite\|Thaler-16}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Graham Cormode