Show simple item record

dc.contributor.authorKasper Green, Larsenen_US
dc.contributor.authorMitzenmacher, Michaelen_US
dc.contributor.authorTsourakakis, Charalamposen_US
dc.coverage.spatialThe Web Conference 2020en_US
dc.date2020-01-10
dc.date.accessioned2020-09-16T17:47:11Z
dc.date.available2020-09-16T17:47:11Z
dc.date.issued2020-04
dc.identifier.citationLarsen Kasper Green, Michael Mitzenmacher, Charalampos Tsourakakis. 2020. "Clustering with a faulty oracle." WWW '20: Proceedings of The Web Conference 2020. Clustering with a faulty oracle. The Web Conference 2020, https://doi.org/10.1145/3366423.3380045
dc.identifier.urihttps://hdl.handle.net/2144/41398
dc.description.abstractClustering, i.e., finding groups in the data, is a problem that permeates multiple fields of science and engineering. Recently, the problem of clustering with a noisy oracle has drawn attention due to various applications including crowdsourced entity resolution [33], and predicting signs of interactions in large-scale online social networks [20, 21]. Here, we consider the following fundamental model for two clusters as proposed by Mitzenmacher and Tsourakakis [28], and Mazumdar and Saha [25]; there exist n items, belonging to two unknown groups. We are allowed to query any pair of nodes whether they belong to the same cluster or not, but the answer to the query is corrupted with some probability . Let 1 > δ = 1 − 2q > 0 be the bias. In this work, we provide a polynomial time algorithm that recovers all signs correctly with high probability in the presence of noise with queries. This is the best known result for this problem for all but tiny δ, improving on the current state-of-the-art due to Mazumdar and Saha [25].en_US
dc.format.extentp. 2831 - 2834en_US
dc.languageEnglish
dc.language.isoen_US
dc.publisherAssociation for Computing Machineryen_US
dc.relation.ispartofWWW '20: Proceedings of The Web Conference 2020
dc.titleClustering with a faulty oracleen_US
dc.typeConference materialsen_US
dc.description.versionAccepted manuscripten_US
dc.identifier.doi10.1145/3366423.3380045
pubs.elements-sourcemanual-entryen_US
pubs.notesEmbargo: Not knownen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusAccepteden_US
dc.identifier.mycv540412


This item appears in the following Collection(s)

Show simple item record