best stream

Invited to Special Issue of Theoretical Computer Science dedicated to TAMC 2009.

Abstract

We study a new model of computation called \textit{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.

PDF

Update:

Apr-12-2009: Deterministic lower bounds are added to the appendix.