Meng–Lin–Yang's optimal-query conjecture for the Rényi-Ulam game

From papers

Let k1k\ge 1 and a,b0a,b\ge 0 satisfy 2k>a2k>a and a+b2a+b\ge 2. Define

ch(a,b)min{q:(q+1)a+b2q}.ch(a,b)\coloneqq\min\big\{q:(q+1)a+b\le 2^q\big\}.

Set

Cmax{ch(a,b),RU0k(2a+b)},C\coloneqq\max\big\{ch(a,b),RU_0^k(2a+b)\big\}, χ0max{x:RU1k(x,ax)C1, xa, xk},\chi_0\coloneqq\max\big\{x:RU_1^k(x,a-x)\le C-1,\ x\le a,\ x\le k\big\}, χ1max{y:RU1k(χ0,y+aχ0)C1, yb, ykχ0}.\chi_1\coloneqq\max\big\{y:RU_1^k(\chi_0,y+a-\chi_0)\le C-1,\ y\le b,\ y\le k-\chi_0\big\}.

Meng–Lin–Yang's conjecture. With these definitions,

RU1k(a,b)=max{C,1+RU1k(aχ0,bχ1+χ0)}.RU_1^k(a,b)=\max\big\{C,1+RU_1^k(a-\chi_0,b-\chi_1+\chi_0)\big\}.

This conjecture concerns the optimal query in the Rényi-Ulam game with restricted-size queries, where RU1k(a,b)RU_1^k(a,b) denotes the relevant one-lie query complexity and the parameters describe the current state. The paper presents it as a conjecture about optimal play; no resolution is given in the supplied text.

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

Ádám Fraknói, Dávid Márton, Dániel Simon and Dániel Lenger, “On the Rényi-Ulam Game with Restricted Size Queries”, arXiv:2104.01664 (2023).

Solutions 0

No solutions have been posted yet.