ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let XnX^n be uniformly distributed over 0,1n\\{0,1\\}^n, let YnY^n be obtained by passing XnX^n through a memoryless binary erasure channel with erasure probability ϵ\epsilon, and let γs(ϵ)\gamma_s(\epsilon) denote the optimal guessing efficiency for moment order ss. A Greedy Dictator function sends the first non-erased bit, using an independent Bernoulli random bit when all bits are erased. Greedy Dictator conjecture. Greedy Dictator functions attain

γs(ϵ)\gamma_s(\epsilon)

for the binary erasure channel. This conjecture is motivated by the local optimality result for ϵ∈[0,1/2]\epsilon\in[0,1/2] and numerical computations for moderate values of nn; the statement concerns simultaneous optimality across the erasure parameter and moment order, and its resolution is not given here.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.