Boston University Libraries OpenBU
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item
    •   OpenBU
    • BU Open Access Articles
    • BU Open Access Articles
    • View Item

    Clustering with a faulty oracle

    Thumbnail
    Date Issued
    2020-04
    Publisher Version
    10.1145/3366423.3380045
    Author(s)
    Kasper Green, Larsen
    Mitzenmacher, Michael
    Tsourakakis, Charalampos
    Share to FacebookShare to TwitterShare by Email
    Export Citation
    Download to BibTex
    Download to EndNote/RefMan (RIS)
    Metadata
    Show full item record
    Permanent Link
    https://hdl.handle.net/2144/41398
    Version
    Accepted manuscript
    Citation (published version)
    Larsen 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
    Abstract
    Clustering, 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].
    Collections
    • CAS: Computer Science: Scholarly Papers [187]
    • BU Open Access Articles [3730]


    Boston University
    Contact Us | Send Feedback | Help
     

     

    Browse

    All of OpenBUCommunities & CollectionsIssue DateAuthorsTitlesSubjectsThis CollectionIssue DateAuthorsTitlesSubjects

    Deposit Materials

    LoginNon-BU Registration

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Boston University
    Contact Us | Send Feedback | Help