Streaming Interactive Protocols for Graphs

In the standard dynamic streaming model most graph problems are hard to approximate in small space, even in the semi-streaming model (where the algorithm is permitted space linear in the number of vertices n). Streaming interactive proofs (SIPs) are a framework for tackling such near-intractable problems by outsourcing computation, so that a computationally limited streaming client (the verifier) hands over a large data set to an untrusted server (the prover) in the cloud and the two parties run a protocol to confirm the correctness of result with high probability.

In this talk, we discuss efficient streaming interactive proofs that can verify maximum matchings exactly. Our results cover all flavors of matchings (bipartite/nonbipartite and weighted). In particular, these are the first approximate results for metric TSP and exact protocols for weighted matchings in any streaming verification model. A considerable portion of this talk will covers the prior technology in the field which we employ, including sum-check protocols, fingerpringing, inverse frequency protocols, and so forth.

This was joint work with Suresh Venkatasubramanian, Samira Daruki and Chitradeep Dutta Roy at the University of Utah.