7 citations · 14 across the 11 of their papers we have counts for
17 papers
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh +1
In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially…
Counting Simplices in Hypergraph Streams
Amit Chakrabarti, Themistoklis Haris
We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied pro…
Adversarially Robust Coloring for Graph Streams
Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl
A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may…
The Element Extraction Problem and the Cost of Determinism and Limited Adaptivity in Linear Queries
Amit Chakrabarti, Manuel Stoeckl
Two widely-used computational paradigms for sublinear algorithms are using linear measurements to perform computations on a high dimensional input and using structured queries to a…
Vertex Ordering Problems in Directed Graph Streams
Amit Chakrabarti, Prantar Ghosh, Andrew McGregor +1
We consider directed graph algorithms in a streaming setting, focusing on problems concerning orderings of the vertices. This includes such fundamental problems as topological sort…
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
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…