Shift-strategy characterization conjecture for the symmetric group

Let Sn\mathbb{S}_n be the symmetric group on nn 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

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.