Massey's same-cluster query lower-bound conjecture
Massey's same-cluster query lower-bound conjecture
Let , let be the label vector, and let a querying scheme use same cluster' queries, each involving two elements ($\Delta=2$). A scheme is **$(1-\delta)$-good** if it correctly recovers at least $(1-\delta)n$ labels for every label vector. **Massey's conjecture.** Any $(1-\delta)$-good scheme with $m$ same cluster' queries must satisfy
The conjecture concerns the inefficiency of linear, same-cluster queries for approximate recovery and is presented as a reformulation of a conjecture by Massey, motivated by the limitation of linear codes as rate-distortion codes. Its resolution is not specified in the source.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Arya Mazumdar and Soumyabrata Pal, “Semisupervised Clustering by Queries and Locally Encodable Source Coding”, arXiv:1904.00507 (2020).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.