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.
References
Primary source
Arya Mazumdar and Soumyabrata Pal, “Semisupervised Clustering by Queries and Locally Encodable Source Coding”, arXiv:1904.00507 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.