Difference between revisions of "Open Problems:47"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(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...")
 
m (updated header)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Annotated Streaming
 
 
|source=bertinoro11
 
|source=bertinoro11
 
|who=Graham Cormode
 
|who=Graham Cormode

Revision as of 01:55, 7 March 2013

Suggested by Graham Cormode
Source Bertinoro 2011
Short link https://sublinear.info/47

In the annotated stream model [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)$?