|
2:00 pm, Lecture Hall 6 Streaming Verification of Graph Computations via Graph Structure Prantar Ghosh Dartmouth College, USA. 18-12-19 Abstract I shall start by describing the basic data streaming and the annotated data streaming models of computation. The latter is also known as verifiable data stream computation. This setting is meant to model outsourced computation e.g., cloud computing, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to trust the prover. As is well established, several problems that admit no sublinear-space algorithms under traditional streaming do allow protocols using a sublinear amount of prover/verifier communication and sublinear-space verification. We give new algorithms in this model for many well-studied graph problems including triangle counting, its generalization to subgraph counting, maximum matching, problems about the existence (or not) of short paths, and testing for an independent set. While some of these problems have been studied before, our results achieve new tradeoffs between space and communication costs that were hitherto unknown. In particular, two of our results disprove explicit conjectures of Thaler (ICALP, 2016) by giving triangle counting and maximum matching algorithms for n-vertex graphs, using o(n) space and o(n^2) communication. This is a joint work with Amit Chakrabarti, and it appeared in APPROX-RANDOM '19.
|
