Amit Chakrabarti, Sagar Kale

We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a ...
more >>>

Amit Chakrabarti, Prantar Ghosh

We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to ... more >>>

Amit Chakrabarti, Prantar Ghosh, Justin Thaler

We study graph computations in an enhanced data streaming setting, where a space-bounded client reading the edge stream of a massive graph may delegate some of its work to a cloud service. We seek algorithms that allow the client to verify a purported proof sent by the cloud service that ... more >>>

Sepehr Assadi, Gillat Kol, Zhijun Zhang

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... more >>>