Best-Order Streaming Model (TAMC’09)

best streamAuthors: Atish Das Sarma, Richard J. Lipton, Danupon Nanongkai

Download: PDFPPT, Journal version (link) (The journal version is *slightly* more updated)

Journal: Invited to Special Issue of Theoretical Computer Science [wiki]

Conference: TAMC 2009: 6th Annual Conference on Theory and Applications of Models of Computation [link]


We study a new model of computation called stream checking on graph problems where a space-limited verifier has to verify a proof sequentially (i.e., it reads the proof as a stream). Moreover, the proof itself is nothing but a reordering of the input data. This model has a close relationship to many models of computation in other areas such as data streams, communication complexity, and proof checking and could be used in applications such as cloud computing.

In this paper we focus on graph problems where the input is a sequence of edges. We show that checking if a graph has a perfect matching is impossible to do deterministically using small space. To contrast this, we show that randomized verifiers are powerful enough to check whether a graph has a perfect matching or is connected.

Update History

[v1] Apr 12, 2009 (Updated conference version in PDF)
[v2] Oct 1, 2009 (Submitted journal version in PDF)
[v3] Nov 22, 2010 (Link to the journal version)


1 Comment »

  1. danupon said

    Related work posted on Mitzenmacher’s blog:

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: