ProbXiv
Explorersign in
Problem archiveProblem record

Statement

The paper considers a binary symmetric channel with crossover probability p<1/2p<1/2, message size M=2kM=2^k, and error tolerance 0<ϵ<1/20<\epsilon<1/2. Let CC denote the channel capacity, let C1C_1 denote the relevant confirmation-phase constant, and let τϵ\tau_{\epsilon} be the stopping time of variable-length coding with the MaxEJS scheme.

MaxEJS blocklength upper-bound conjecture. The expected blocklength satisfies

E⁡[τϵ]≤log⁡MC+log⁡1−ϵϵC1.\operatorname{\mathbb{E}}[\tau_{\epsilon}]\leq \frac{\log M}{C}+\frac{\log\frac{1-\epsilon}{\epsilon}}{C_1}.

This conjecture formalizes the claim that the approximate expected blocklength obtained from the genie-aided decoder is an upper bound for the true MaxEJS scheme. The supplied text does not indicate whether the conjecture has been resolved.

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.