5 papers
Counting Triangles in Graph Streams with Repeatable and Forgettable Edges
Sourav Chakraborty, Debarshi Chanda, Arijit Ghosh +3
Most existing graph streaming algorithms assume the ideal scenario where each edge arrives only once. Real-world graph streams, such as communication or transaction logs, often con…
Computing over Data Streams using Catalytic Space
Ripley Becker, Sourav Chakraborty, Debarshi Chanda +2
We introduce a streaming model with \emph{catalytic memory}, an auxiliary workspace that must be returned to its initial state at the end of the computation. We show that catalytic…
Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression
Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +3
Assessing whether a sample survey credibly represents the population is a critical question for ensuring the validity of downstream research. Generally, this problem reduces to est…
Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
Debabrota Basu, Debarshi Chanda
Resource-efficiently computing representations of probability distributions and the distances between them while only having access to the samples is a fundamental and useful probl…
Testing Credibility of Public and Private Surveys through the Lens of Regression
Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +3
Testing whether a sample survey is a credible representation of the population is an important question to ensure the validity of any downstream research. While this problem, in ge…