Shift-strategy characterization conjecture for the symmetric group
Shift-strategy characterization conjecture for the symmetric group
Let be the symmetric group on elements. A shift strategy is the strategy described in the paper in which the message classes are determined by the cyclic shifts, with Alice indicating a shift agreeing with the input permutation at the maximum number of positions. An optimal strategy is one attaining the maximum success probability.
Shift-strategy characterization conjecture. Every optimal strategy is a shift strategy.
This conjecture is a more restrictive structural characterization than the Latin-strategy conjecture. The paper presents it as an open question; no proof or counterexample is supplied.
Sources & referencesView supporting material
Primary source
Artur Czumaj, George Kontogeorgiou and Mike Paterson, “Haystack Hunting Hints and Locker Room Communication”, arXiv:2008.11448 (2021).
Additional references
2 papers in this index state this conjecture (2015–2020). The statement above is taken from the most recent of them; the others are arXiv:1502.00158.
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
Sign in to submit a solution.
No solutions have been posted yet.