Massey's same-cluster query lower-bound conjecture

About 7 years old · traced to

Let k=2k=2, let \bfX∈{0,1}n\bfX\in\{0,1\}^n be the label vector, and let a querying scheme use mm 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

δ≥p(1−mnH(p)).\delta \ge p\left(1-\frac{m}{nH(p)}\right).

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

Never refreshed

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.