37 citations · 59 across the 4 of their papers we have counts for
6 papers
The Geometric Block Model
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal +1
To capture the inherent geometric features of many community detection problems, we propose to use a new random graph model of communities that we call a Geometric Block Model. The…
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Karl Bringmann, Fabrizio Grandoni, Barna Saha +1
It is a major open problem whether the -product of two matrices has a truly sub-cubic (i.e. for ) time algorithm, in particular since it is…
Query Complexity of Clustering with Side Information
Arya Mazumdar, Barna Saha
Suppose, we are given a set of elements to be clustered into (unknown) clusters, and an oracle/expert labeler that can interactively answer pair-wise queries of the form, "…
Clustering with Noisy Queries
Arya Mazumdar, Barna Saha
In this paper, we initiate a rigorous theoretical study of clustering with noisy queries (or a faulty oracle). Given a set of elements, our goal is to recover the true clusteri…
A Theoretical Analysis of First Heuristics of Crowdsourced Entity Resolution
Arya Mazumdar, Barna Saha
Entity resolution (ER) is the task of identifying all records in a database that refer to the same underlying entity, and are therefore duplicates of each other. Due to inherent am…
Clustering Via Crowdsourcing
Arya Mazumdar, Barna Saha
In recent years, crowdsourcing, aka human aided computation has emerged as an effective platform for solving problems that are considered complex for machines alone. Using human is…