Massey's same-cluster query lower-bound conjecture

From papers

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(1mnH(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.

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

No solutions have been posted yet.