2 citations · 2 across the 3 of their papers we have counts for
7 papers
A New Dynamic Algorithm for Densest Subhypergraphs
Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari +1
Computing a dense subgraph is a fundamental problem in graph mining, with a diverse set of applications ranging from electronic commerce to community detection in social networks.…
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…
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…
New Verification Schemes for Frequency-Based Functions on Data Streams
Prantar Ghosh
We study the general problem of computing frequency-based functions, i.e., the sum of any given function of data stream frequencies. Special cases include fundamental data stream p…
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…
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
Suman K. Bera, Amit Chakrabarti, Prantar Ghosh
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model…