Streaming computations with a loquacious prover

Abstract

We define a new model of data streaming algorithms that employ a prover/helper to outsource difficult computations in a verifiable way. While for the verifier the usual time (per symbol read) and space constraints of the data streaming model are in place, the prover has unbounded space. Both parties cannot look into the future (i.e., do not know data arriving later). Previous work on such models either severely restricted the total communication between the prover and the verifier, or extended the computation by a long annotation that has to be streamed from the prover to the verifier offline after the original stream has ended, delaying the computation of the result. We argue that restricting the total communication severely is unnatural and investigate a model that only bounds the communication overhead, i.e., the amount of communication sent from the prover to the verifier per symbol of the data stream. This allows for vastly more communication between prover and verifier while maintaining the online nature of the model (in particular long annotations sent after the stream has ended are not allowed). Relaxing the communication requirement allows us to find simple algorithms for problems like the Longest Increasing Subsequence Problem (LIS), finding the Median, and for deciding whether the rank of a matrix is full or not. All our algorithms have a similar structure with phases whose length shrinks geometrically, and phase i being used to verify certain properties of the stream up to phase i-1 using re-streaming of parts of the previous stream. The challenge in each case is to tie the different phases together.