9 papers
Sublinear Algorithms for Estimating the Number of Hyperedges in Arbitrary Hypergraphs
Deeparnab Chakrabarty, Cooper LaPorte, C. Seshadhri
We study the problem of estimating the number of hyperedges in an arbitrary -vertex hypergraph using sublinear in queries. Note that the number of hyperedges, , can be ex…
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Deeparnab Chakrabarty, Aditi Dudeja, David Saulpic
We study the round complexity of learning a hidden partition of an -element universe using PAIR queries: PAIR() tells us whether and belong to the sam…
Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles
Deeparnab Chakrabarty, Hang Liao
We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal -query connectivity algorithms, hypergraphs face…
Counting hypertriangles through hypergraph orientations
Daniel Paul-Pena, Vaishali Surianarayanan, Deeparnab Chakrabarty +1
Counting the number of small patterns is a central task in network analysis. While this problem is well studied for graphs, many real-world datasets are naturally modeled as hyperg…
Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
Lorenzo Beretta, Deeparnab Chakrabarty, C. Seshadhri
We revisit the problem of designing sublinear algorithms for estimating the average degree of an -vertex graph. The standard access model for graphs allows for the following que…
Clustering in Varying Metrics
Deeparnab Chakrabarty, Jonathan Conroy, Ankita Sarkar
We introduce the aggregated clustering problem, where one is given instances of a center-based clustering task over the same points, but under different metrics. The goal i…