Symmetrized Li–Médard conjecture

Let XX be uniformly distributed on {0,1}n\{0,1\}^n, let YY be obtained from XX through a binary symmetric channel with crossover probability 0<p<120<p<\frac{1}{2}, and let f:{0,1}n{0,1}f:\{0,1\}^n\to\{0,1\} be balanced, meaning E[f(Y)]=12\mathbb{E}[f(Y)]=\frac{1}{2}. Define Tpf(x)=P(f(Y)=1X=x)T_pf(x)=\mathbb{P}(f(Y)=1\mid X=x), let f0f_0 be a dictatorship function, and set

Nαsym(f)=x{0,1}n((Tpf(x))α+(1Tpf(x))α).N^\mathsf{sym}_\alpha(f)=\sum_{x\in\{0,1\}^n}\left((T_pf(x))^\alpha+(1-T_pf(x))^\alpha\right).

A Li–Médard conjecture. For any balanced ff,

Nαsym(f)Nαsym(f0)N^\mathsf{sym}_\alpha(f)\leq N^\mathsf{sym}_\alpha(f_0)

for 1α21\leq\alpha\leq2. This symmetrized conjecture is the formulation linked in the paper to the mutual-information version of the Courtade–Kumar conjecture.

Sources & referencesView supporting material

Primary source

Leighton Pate Barnes and Ayfer Özgür, “The Courtade-Kumar Most Informative Boolean Function Conjecture and a Symmetrized Li-Médard Conjecture are Equivalent”, arXiv:2004.01277 (2020).

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.