Editing Open Problems:47

{{Header
|title=Annotated Streaming
|source=bertinoro11
|who=Graham Cormode
}}
In the annotated stream model {{cite|ChakrabartiCM-09}}, a stream is 
augmented with &lsquo;annotation&rsquo;, 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)$?